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_create_node_params (new_node
);
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 true if LAT1 and LAT2 are equal. */
188 ipcp_lats_are_equal (struct ipcp_lattice
*lat1
, struct ipcp_lattice
*lat2
)
190 gcc_assert (ipcp_lat_is_const (lat1
) && ipcp_lat_is_const (lat2
));
191 if (lat1
->type
!= lat2
->type
)
194 if (operand_equal_p (lat1
->constant
, lat2
->constant
, 0))
200 /* Compute Meet arithmetics:
201 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
203 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
204 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
206 ipa_lattice_meet (struct ipcp_lattice
*res
, struct ipcp_lattice
*lat1
,
207 struct ipcp_lattice
*lat2
)
209 if (lat1
->type
== IPA_BOTTOM
|| lat2
->type
== IPA_BOTTOM
)
211 res
->type
= IPA_BOTTOM
;
214 if (lat1
->type
== IPA_TOP
)
216 res
->type
= lat2
->type
;
217 res
->constant
= lat2
->constant
;
220 if (lat2
->type
== IPA_TOP
)
222 res
->type
= lat1
->type
;
223 res
->constant
= lat1
->constant
;
226 if (!ipcp_lats_are_equal (lat1
, lat2
))
228 res
->type
= IPA_BOTTOM
;
231 res
->type
= lat1
->type
;
232 res
->constant
= lat1
->constant
;
235 /* Return the lattice corresponding to the Ith formal parameter of the function
236 described by INFO. */
237 static inline struct ipcp_lattice
*
238 ipcp_get_ith_lattice (struct ipa_node_params
*info
, int i
)
240 return &(info
->ipcp_lattices
[i
]);
243 /* Given the jump function JFUNC, compute the lattice LAT that describes the
244 value coming down the callsite. INFO describes the caller node so that
245 pass-through jump functions can be evaluated. */
247 ipcp_lattice_from_jfunc (struct ipa_node_params
*info
, struct ipcp_lattice
*lat
,
248 struct ipa_jump_func
*jfunc
)
250 if (jfunc
->type
== IPA_UNKNOWN
)
251 lat
->type
= IPA_BOTTOM
;
252 else if (jfunc
->type
== IPA_CONST
)
254 lat
->type
= IPA_CONST_VALUE
;
255 lat
->constant
= jfunc
->value
.constant
;
257 else if (jfunc
->type
== IPA_CONST_REF
)
259 lat
->type
= IPA_CONST_VALUE_REF
;
260 lat
->constant
= jfunc
->value
.constant
;
262 else if (jfunc
->type
== IPA_PASS_THROUGH
)
264 struct ipcp_lattice
*caller_lat
;
266 caller_lat
= ipcp_get_ith_lattice (info
, jfunc
->value
.formal_id
);
267 lat
->type
= caller_lat
->type
;
268 lat
->constant
= caller_lat
->constant
;
272 /* True when OLD and NEW values are not the same. */
274 ipcp_lattice_changed (struct ipcp_lattice
*old
, struct ipcp_lattice
*new)
276 if (old
->type
== new->type
)
278 if (!ipcp_lat_is_const (old
))
280 if (ipcp_lats_are_equal (old
, new))
286 /* Print all ipcp_lattices of all functions to F. */
288 ipcp_print_all_lattices (FILE * f
)
290 struct cgraph_node
*node
;
293 fprintf (f
, "\nLATTICE PRINT\n");
294 for (node
= cgraph_nodes
; node
; node
= node
->next
)
296 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
297 fprintf (f
, "Printing lattices %s:\n", cgraph_node_name (node
));
298 count
= ipa_get_param_count (info
);
299 for (i
= 0; i
< count
; i
++)
301 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
302 if (lat
->type
== IPA_CONST_VALUE
|| lat
->type
== IPA_CONST_VALUE_REF
)
304 fprintf (f
, " param [%d]: ", i
);
305 fprintf (f
, "type is CONST ");
306 print_generic_expr (f
, lat
->constant
, 0);
309 else if (lat
->type
== IPA_TOP
)
310 fprintf (f
, "param [%d]: type is TOP \n", i
);
312 fprintf (f
, "param [%d]: type is BOTTOM \n", i
);
317 /* Initialize ipcp_lattices array. The lattices corresponding to supported
318 types (integers, real types and Fortran constants defined as const_decls)
319 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
321 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
324 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
326 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
327 ipa_get_param_count (info
));
328 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
330 tree parm_tree
= ipa_get_ith_param (info
, i
);
331 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
333 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree
))
334 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree
))
335 || POINTER_TYPE_P (TREE_TYPE (parm_tree
)))
338 lat
->type
= IPA_BOTTOM
;
342 /* Create a new assignment statement and make it the first statement in the
343 function. PARM1 is the lhs of the assignment and VAL is the rhs. */
345 constant_val_insert (tree parm1
, tree val
)
347 tree init_stmt
= NULL
;
350 init_stmt
= build_gimple_modify_stmt (parm1
, val
);
354 e_step
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
));
355 bsi_insert_on_edge_immediate (e_step
, init_stmt
);
359 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
362 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
364 tree const_val
= NULL
;
366 gcc_assert (ipcp_lat_is_const (lat
));
367 const_val
= fold_convert (tree_type
, lat
->constant
);
371 /* Build the tree representing the constant and call constant_val_insert(). */
373 ipcp_propagate_one_const (struct cgraph_node
*node
, int param
,
374 struct ipcp_lattice
*lat
)
380 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (node
));
381 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), param
);
382 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
383 constant_val_insert (parm_tree
, const_val
);
386 /* Compute the proper scale for NODE. It is the ratio between the number of
387 direct calls (represented on the incoming cgraph_edges) and sum of all
388 invocations of NODE (represented as count in cgraph_node). */
390 ipcp_compute_node_scale (struct cgraph_node
*node
)
393 struct cgraph_edge
*cs
;
396 /* Compute sum of all counts of callers. */
397 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
399 if (node
->count
== 0)
400 ipcp_set_node_scale (node
, 0);
402 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
405 /* Initialization and computation of IPCP data structures. This is the initial
406 intraprocedural analysis of functions, which gathers information to be
407 propagated later on. */
409 ipcp_init_stage (void)
411 struct cgraph_node
*node
;
412 struct cgraph_edge
*cs
;
414 for (node
= cgraph_nodes
; node
; node
= node
->next
)
416 ipa_count_formal_params (node
);
417 ipa_create_param_decls_array (node
);
418 ipcp_initialize_node_lattices (node
);
419 ipa_detect_param_modifications (node
);
420 ipcp_compute_node_scale (node
);
422 for (node
= cgraph_nodes
; node
; node
= node
->next
)
424 /* building jump functions */
425 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
427 ipa_count_arguments (cs
);
428 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
429 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
431 /* Handle cases of functions with
432 a variable number of parameters. */
433 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
436 ipa_compute_jump_functions (cs
);
441 /* Return true if there are some formal parameters whose value is IPA_TOP (in
442 the whole compilation unit). Change their values to IPA_BOTTOM, since they
443 most probably get their values from outside of this compilation unit. */
445 ipcp_change_tops_to_bottom (void)
448 struct cgraph_node
*node
;
452 for (node
= cgraph_nodes
; node
; node
= node
->next
)
454 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
455 count
= ipa_get_param_count (info
);
456 for (i
= 0; i
< count
; i
++)
458 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
459 if (lat
->type
== IPA_TOP
)
462 lat
->type
= IPA_BOTTOM
;
469 /* Interprocedural analysis. The algorithm propagates constants from the
470 caller's parameters to the callee's arguments. */
472 ipcp_propagate_stage (void)
475 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
476 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
477 struct ipcp_lattice
*dest_lat
;
478 struct cgraph_edge
*cs
;
479 struct ipa_jump_func
*jump_func
;
480 struct ipa_func_list
*wl
;
483 /* Initialize worklist to contain all functions. */
484 wl
= ipa_init_func_list ();
487 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
488 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
490 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
492 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
493 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
495 if (ipa_is_called_with_var_arguments (callee_info
))
498 count
= ipa_get_cs_argument_count (args
);
499 for (i
= 0; i
< count
; i
++)
501 jump_func
= ipa_get_ith_jump_func (args
, i
);
502 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
503 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
504 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
505 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
507 dest_lat
->type
= new_lat
.type
;
508 dest_lat
->constant
= new_lat
.constant
;
509 ipa_push_func_to_list (&wl
, cs
->callee
);
516 /* Call the constant propagation algorithm and re-call it if necessary
517 (if there are undetermined values left). */
519 ipcp_iterate_stage (void)
521 ipcp_propagate_stage ();
522 if (ipcp_change_tops_to_bottom ())
523 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
524 This change should be propagated. */
525 ipcp_propagate_stage ();
528 /* Check conditions to forbid constant insertion to function described by
531 ipcp_node_not_modifiable_p (struct cgraph_node
*node
)
533 /* ??? Handle pending sizes case. */
534 if (DECL_UNINLINABLE (node
->decl
))
539 /* Print ipa_jump_func data structures to F. */
541 ipcp_print_all_jump_functions (FILE * f
)
543 struct cgraph_node
*node
;
545 struct cgraph_edge
*cs
;
546 struct ipa_jump_func
*jump_func
;
547 enum jump_func_type type
;
550 fprintf (f
, "\nCALLSITE PARAM PRINT\n");
551 for (node
= cgraph_nodes
; node
; node
= node
->next
)
553 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
555 fprintf (f
, "callsite %s ", cgraph_node_name (node
));
556 fprintf (f
, "-> %s :: \n", cgraph_node_name (cs
->callee
));
558 if (ipa_is_called_with_var_arguments (IPA_NODE_REF (cs
->callee
)))
561 count
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
562 for (i
= 0; i
< count
; i
++)
564 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
565 type
= jump_func
->type
;
567 fprintf (f
, " param %d: ", i
);
568 if (type
== IPA_UNKNOWN
)
569 fprintf (f
, "UNKNOWN\n");
570 else if (type
== IPA_CONST
|| type
== IPA_CONST_REF
)
572 info_type
= jump_func
->value
.constant
;
573 fprintf (f
, "CONST : ");
574 print_generic_expr (f
, info_type
, 0);
577 else if (type
== IPA_PASS_THROUGH
)
579 fprintf (f
, "PASS THROUGH : ");
580 fprintf (f
, "%d\n", jump_func
->value
.formal_id
);
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
)
595 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
596 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
597 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
601 /* Print counts of all cgraph nodes. */
603 ipcp_print_func_profile_counts (FILE * f
)
605 struct cgraph_node
*node
;
607 for (node
= cgraph_nodes
; node
; node
= node
->next
)
609 fprintf (f
, "function %s: ", cgraph_node_name (node
));
610 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
611 " \n", (HOST_WIDE_INT
) node
->count
);
615 /* Print counts of all cgraph edges. */
617 ipcp_print_call_profile_counts (FILE * f
)
619 struct cgraph_node
*node
;
620 struct cgraph_edge
*cs
;
622 for (node
= cgraph_nodes
; node
; node
= node
->next
)
624 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
626 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
627 cgraph_node_name (cs
->callee
));
628 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
629 (HOST_WIDE_INT
) cs
->count
);
634 /* Print all counts and probabilities of cfg edges of all functions. */
636 ipcp_print_edge_profiles (FILE * f
)
638 struct cgraph_node
*node
;
643 for (node
= cgraph_nodes
; node
; node
= node
->next
)
645 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
646 if (DECL_SAVED_TREE (node
->decl
))
649 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
650 fprintf (f
, "ENTRY: ");
651 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
652 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
655 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
658 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
660 fprintf (f
, "edge ENTRY -> EXIT, Count");
662 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
663 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
664 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
667 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
669 fprintf (f
, "bb[%d]: ", bb
->index
);
670 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
671 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
672 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
675 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
677 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
679 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
681 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
682 (HOST_WIDE_INT
) e
->count
, e
->probability
);
689 /* Print counts and frequencies for all basic blocks of all functions. */
691 ipcp_print_bb_profiles (FILE * f
)
694 struct cgraph_node
*node
;
696 for (node
= cgraph_nodes
; node
; node
= node
->next
)
698 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
702 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
703 fprintf (f
, "ENTRY: Count");
704 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
705 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
708 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
710 fprintf (f
, "bb[%d]: Count", bb
->index
);
711 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
712 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
716 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
717 fprintf (f
, "EXIT: Count");
718 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
719 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
726 /* Print all IPCP data structures to F. */
728 ipcp_print_all_structures (FILE * f
)
730 ipcp_print_all_lattices (f
);
731 ipcp_function_scale_print (f
);
732 ipa_print_all_tree_maps (f
);
733 ipa_print_all_params_modified (f
);
734 ipcp_print_all_jump_functions (f
);
737 /* Print profile info for all functions. */
739 ipcp_print_profile_data (FILE * f
)
741 fprintf (f
, "\nNODE COUNTS :\n");
742 ipcp_print_func_profile_counts (f
);
743 fprintf (f
, "\nCS COUNTS stage:\n");
744 ipcp_print_call_profile_counts (f
);
745 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
746 ipcp_print_bb_profiles (f
);
747 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
748 ipcp_print_edge_profiles (f
);
751 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
752 processed by versioning, which operates according to the flags set.
753 PARM_TREE is the formal parameter found to be constant. LAT represents the
755 static struct ipa_replace_map
*
756 ipcp_create_replace_map (struct function
*func
, tree parm_tree
,
757 struct ipcp_lattice
*lat
)
759 struct ipa_replace_map
*replace_map
;
762 replace_map
= XCNEW (struct ipa_replace_map
);
763 gcc_assert (ipcp_lat_is_const (lat
));
764 if (lat
->type
!= IPA_CONST_VALUE_REF
765 && is_gimple_reg (parm_tree
) && gimple_default_def (func
, parm_tree
)
766 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func
,
770 fprintf (dump_file
, "replacing param with const\n");
771 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
772 replace_map
->old_tree
=gimple_default_def (func
, parm_tree
);
773 replace_map
->new_tree
= const_val
;
774 replace_map
->replace_p
= true;
775 replace_map
->ref_p
= false;
779 replace_map
->old_tree
= NULL
;
780 replace_map
->new_tree
= NULL
;
781 replace_map
->replace_p
= false;
782 replace_map
->ref_p
= false;
788 /* Return true if this callsite should be redirected to the original callee
789 (instead of the cloned one). */
791 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
793 struct ipa_node_params
*orig_callee_info
;
795 struct ipa_jump_func
*jump_func
;
797 orig_callee_info
= IPA_NODE_REF (ipcp_get_orig_node (cs
->callee
));
798 count
= ipa_get_param_count (orig_callee_info
);
799 for (i
= 0; i
< count
; i
++)
801 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
802 if (ipcp_lat_is_const (lat
))
804 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
805 if (!ipcp_lat_is_const (lat
))
813 /* Fix the callsites and the call graph after function cloning was done. */
815 ipcp_update_callgraph (void)
817 struct cgraph_node
*node
, *orig_callee
;
818 struct cgraph_edge
*cs
;
820 for (node
= cgraph_nodes
; node
; node
= node
->next
)
822 /* want to fix only original nodes */
823 if (ipcp_node_is_clone (node
))
825 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
826 if (ipcp_node_is_clone (cs
->callee
))
828 /* Callee is a cloned node */
829 orig_callee
= ipcp_get_orig_node (cs
->callee
);
830 if (ipcp_need_redirect_p (cs
))
832 cgraph_redirect_edge_callee (cs
, orig_callee
);
833 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (cs
->call_stmt
)),
841 /* Update all cfg basic blocks in NODE according to SCALE. */
843 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
847 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
848 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
851 /* Update all cfg edges in NODE according to SCALE. */
853 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
859 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
860 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
861 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
864 /* Update profiling info for versioned functions and the functions they were
867 ipcp_update_profiling (void)
869 struct cgraph_node
*node
, *orig_node
;
870 gcov_type scale
, scale_complement
;
871 struct cgraph_edge
*cs
;
873 for (node
= cgraph_nodes
; node
; node
= node
->next
)
875 if (ipcp_node_is_clone (node
))
877 orig_node
= ipcp_get_orig_node (node
);
878 scale
= ipcp_get_node_scale (orig_node
);
879 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
880 scale_complement
= REG_BR_PROB_BASE
- scale
;
882 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
883 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
884 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
885 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
886 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
887 ipcp_update_bb_counts (node
, scale
);
888 ipcp_update_bb_counts (orig_node
, scale_complement
);
889 ipcp_update_edges_counts (node
, scale
);
890 ipcp_update_edges_counts (orig_node
, scale_complement
);
895 /* Propagate the constant parameters found by ipcp_iterate_stage()
896 to the function's code. */
898 ipcp_insert_stage (void)
900 struct cgraph_node
*node
, *node1
= NULL
;
902 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
903 varray_type replace_trees
;
904 struct cgraph_edge
*cs
;
905 int node_callers
, count
;
907 struct ipa_replace_map
*replace_param
;
909 for (node
= cgraph_nodes
; node
; node
= node
->next
)
911 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
912 /* Propagation of the constant is forbidden in
913 certain conditions. */
914 if (!node
->analyzed
|| ipcp_node_not_modifiable_p (node
)
915 || ipa_is_called_with_var_arguments (info
))
918 count
= ipa_get_param_count (info
);
919 for (i
= 0; i
< count
; i
++)
921 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
922 if (ipcp_lat_is_const (lat
))
925 if (const_param
== 0)
927 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
928 for (i
= 0; i
< count
; i
++)
930 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
931 if (ipcp_lat_is_const (lat
))
933 parm_tree
= ipa_get_ith_param (info
, i
);
935 ipcp_create_replace_map (DECL_STRUCT_FUNCTION (node
->decl
),
937 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
940 /* Compute how many callers node has. */
942 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
944 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
945 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
946 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
947 /* Redirecting all the callers of the node to the
948 new versioned node. */
950 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
951 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
952 VARRAY_CLEAR (replace_trees
);
956 fprintf (dump_file
, "versioned function %s\n",
957 cgraph_node_name (node
));
958 ipcp_init_cloned_node (node
, node1
);
961 push_cfun (DECL_STRUCT_FUNCTION (node1
->decl
));
962 tree_register_cfg_hooks ();
963 current_function_decl
= node1
->decl
;
965 for (i
= 0; i
< count
; i
++)
967 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
968 if (ipcp_lat_is_const (lat
))
970 parm_tree
= ipa_get_ith_param (info
, i
);
971 if (lat
->type
!= IPA_CONST_VALUE_REF
972 && !is_gimple_reg (parm_tree
))
973 ipcp_propagate_one_const (node1
, i
, lat
);
976 if (gimple_in_ssa_p (cfun
))
978 update_ssa (TODO_update_ssa
);
979 #ifdef ENABLE_CHECKING
983 free_dominance_info (CDI_DOMINATORS
);
984 free_dominance_info (CDI_POST_DOMINATORS
);
986 current_function_decl
= NULL
;
989 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
991 ipcp_update_callgraph ();
992 ipcp_update_profiling ();
995 /* The IPCP driver. */
1000 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1001 ipa_create_all_node_params ();
1002 ipa_create_all_edge_args ();
1003 /* 1. Call the init stage to initialize
1004 the ipa_node_params and ipa_edge_args structures. */
1008 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1009 ipcp_print_all_structures (dump_file
);
1011 /* 2. Do the interprocedural propagation. */
1012 ipcp_iterate_stage ();
1015 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1016 ipcp_print_all_structures (dump_file
);
1017 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1018 ipcp_print_profile_data (dump_file
);
1020 /* 3. Insert the constants found to the functions. */
1021 ipcp_insert_stage ();
1024 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1025 ipcp_print_profile_data (dump_file
);
1027 /* Free all IPCP structures. */
1028 ipa_free_all_node_params ();
1029 ipa_free_all_edge_args ();
1031 fprintf (dump_file
, "\nIPA constant propagation end\n");
1032 cgraph_remove_unreachable_nodes (true, NULL
);
1036 /* Gate for IPCP optimization. */
1038 cgraph_gate_cp (void)
1043 struct simple_ipa_opt_pass pass_ipa_cp
=
1048 cgraph_gate_cp
, /* gate */
1049 ipcp_driver
, /* execute */
1052 0, /* static_pass_number */
1053 TV_IPA_CONSTANT_PROP
, /* tv_id */
1054 0, /* properties_required */
1055 PROP_trees
, /* properties_provided */
1056 0, /* properties_destroyed */
1057 0, /* todo_flags_start */
1058 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */