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 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
;
300 info
= IPA_NODE_REF (node
);
301 fprintf (f
, "Printing lattices %s:\n", cgraph_node_name (node
));
302 count
= ipa_get_param_count (info
);
303 for (i
= 0; i
< count
; i
++)
305 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
306 if (lat
->type
== IPA_CONST_VALUE
|| lat
->type
== IPA_CONST_VALUE_REF
)
308 fprintf (f
, " param [%d]: ", i
);
309 fprintf (f
, "type is CONST ");
310 print_generic_expr (f
, lat
->constant
, 0);
313 else if (lat
->type
== IPA_TOP
)
314 fprintf (f
, "param [%d]: type is TOP \n", i
);
316 fprintf (f
, "param [%d]: type is BOTTOM \n", i
);
321 /* Initialize ipcp_lattices array. The lattices corresponding to supported
322 types (integers, real types and Fortran constants defined as const_decls)
323 are initialized to IPA_TOP, the rest of them to IPA_BOTTOM. */
325 ipcp_initialize_node_lattices (struct cgraph_node
*node
)
328 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
330 info
->ipcp_lattices
= XCNEWVEC (struct ipcp_lattice
,
331 ipa_get_param_count (info
));
332 for (i
= 0; i
< ipa_get_param_count (info
) ; i
++)
334 tree parm_tree
= ipa_get_ith_param (info
, i
);
335 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
337 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree
))
338 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree
))
339 || POINTER_TYPE_P (TREE_TYPE (parm_tree
)))
342 lat
->type
= IPA_BOTTOM
;
346 /* Create a new assignment statement and make it the first statement in the
347 function. PARM1 is the lhs of the assignment and VAL is the rhs. */
349 constant_val_insert (tree parm1
, tree val
)
351 tree init_stmt
= NULL
;
354 init_stmt
= build_gimple_modify_stmt (parm1
, val
);
358 e_step
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
));
359 bsi_insert_on_edge_immediate (e_step
, init_stmt
);
363 /* build INTEGER_CST tree with type TREE_TYPE and value according to LAT.
366 build_const_val (struct ipcp_lattice
*lat
, tree tree_type
)
368 tree const_val
= NULL
;
370 gcc_assert (ipcp_lat_is_const (lat
));
371 const_val
= fold_convert (tree_type
, lat
->constant
);
375 /* Build the tree representing the constant and call constant_val_insert(). */
377 ipcp_propagate_one_const (struct cgraph_node
*node
, int param
,
378 struct ipcp_lattice
*lat
)
384 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (node
));
385 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), param
);
386 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
387 constant_val_insert (parm_tree
, const_val
);
390 /* Compute the proper scale for NODE. It is the ratio between the number of
391 direct calls (represented on the incoming cgraph_edges) and sum of all
392 invocations of NODE (represented as count in cgraph_node). */
394 ipcp_compute_node_scale (struct cgraph_node
*node
)
397 struct cgraph_edge
*cs
;
400 /* Compute sum of all counts of callers. */
401 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
403 if (node
->count
== 0)
404 ipcp_set_node_scale (node
, 0);
406 ipcp_set_node_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
409 /* Initialization and computation of IPCP data structures. This is the initial
410 intraprocedural analysis of functions, which gathers information to be
411 propagated later on. */
413 ipcp_init_stage (void)
415 struct cgraph_node
*node
;
416 struct cgraph_edge
*cs
;
418 for (node
= cgraph_nodes
; node
; node
= node
->next
)
422 /* Unreachable nodes should have been eliminated before ipcp. */
423 gcc_assert (node
->needed
|| node
->reachable
);
425 ipa_count_formal_params (node
);
426 ipa_create_param_decls_array (node
);
427 ipcp_initialize_node_lattices (node
);
428 ipa_detect_param_modifications (node
);
429 ipcp_compute_node_scale (node
);
431 for (node
= cgraph_nodes
; node
; node
= node
->next
)
435 /* building jump functions */
436 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
438 if (!cs
->callee
->analyzed
)
440 ipa_count_arguments (cs
);
441 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
442 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
444 /* Handle cases of functions with
445 a variable number of parameters. */
446 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
449 ipa_compute_jump_functions (cs
);
454 /* Return true if there are some formal parameters whose value is IPA_TOP (in
455 the whole compilation unit). Change their values to IPA_BOTTOM, since they
456 most probably get their values from outside of this compilation unit. */
458 ipcp_change_tops_to_bottom (void)
461 struct cgraph_node
*node
;
465 for (node
= cgraph_nodes
; node
; node
= node
->next
)
467 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
468 count
= ipa_get_param_count (info
);
469 for (i
= 0; i
< count
; i
++)
471 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
472 if (lat
->type
== IPA_TOP
)
475 lat
->type
= IPA_BOTTOM
;
482 /* Interprocedural analysis. The algorithm propagates constants from the
483 caller's parameters to the callee's arguments. */
485 ipcp_propagate_stage (void)
488 struct ipcp_lattice inc_lat
= { IPA_BOTTOM
, NULL
};
489 struct ipcp_lattice new_lat
= { IPA_BOTTOM
, NULL
};
490 struct ipcp_lattice
*dest_lat
;
491 struct cgraph_edge
*cs
;
492 struct ipa_jump_func
*jump_func
;
493 struct ipa_func_list
*wl
;
496 ipa_check_create_node_params ();
497 ipa_check_create_edge_args ();
498 /* Initialize worklist to contain all functions. */
499 wl
= ipa_init_func_list ();
502 struct cgraph_node
*node
= ipa_pop_func_from_list (&wl
);
503 struct ipa_node_params
*info
= IPA_NODE_REF (node
);
505 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
507 struct ipa_node_params
*callee_info
= IPA_NODE_REF (cs
->callee
);
508 struct ipa_edge_args
*args
= IPA_EDGE_REF (cs
);
510 if (ipa_is_called_with_var_arguments (callee_info
))
513 count
= ipa_get_cs_argument_count (args
);
514 for (i
= 0; i
< count
; i
++)
516 jump_func
= ipa_get_ith_jump_func (args
, i
);
517 ipcp_lattice_from_jfunc (info
, &inc_lat
, jump_func
);
518 dest_lat
= ipcp_get_ith_lattice (callee_info
, i
);
519 ipa_lattice_meet (&new_lat
, &inc_lat
, dest_lat
);
520 if (ipcp_lattice_changed (&new_lat
, dest_lat
))
522 dest_lat
->type
= new_lat
.type
;
523 dest_lat
->constant
= new_lat
.constant
;
524 ipa_push_func_to_list (&wl
, cs
->callee
);
531 /* Call the constant propagation algorithm and re-call it if necessary
532 (if there are undetermined values left). */
534 ipcp_iterate_stage (void)
536 ipcp_propagate_stage ();
537 if (ipcp_change_tops_to_bottom ())
538 /* Some lattices have changed from IPA_TOP to IPA_BOTTOM.
539 This change should be propagated. */
540 ipcp_propagate_stage ();
543 /* Check conditions to forbid constant insertion to function described by
546 ipcp_node_not_modifiable_p (struct cgraph_node
*node
)
548 /* ??? Handle pending sizes case. */
549 if (DECL_UNINLINABLE (node
->decl
))
554 /* Print ipa_jump_func data structures to F. */
556 ipcp_print_all_jump_functions (FILE * f
)
558 struct cgraph_node
*node
;
560 struct cgraph_edge
*cs
;
561 struct ipa_jump_func
*jump_func
;
562 enum jump_func_type type
;
565 fprintf (f
, "\nCALLSITE PARAM PRINT\n");
566 for (node
= cgraph_nodes
; node
; node
= node
->next
)
571 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
573 fprintf (f
, "callsite %s ", cgraph_node_name (node
));
574 fprintf (f
, "-> %s :: \n", cgraph_node_name (cs
->callee
));
576 if (!ipa_edge_args_info_available_for_edge_p (cs
)
577 || ipa_is_called_with_var_arguments (IPA_NODE_REF (cs
->callee
)))
580 count
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
581 for (i
= 0; i
< count
; i
++)
583 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
584 type
= jump_func
->type
;
586 fprintf (f
, " param %d: ", i
);
587 if (type
== IPA_UNKNOWN
)
588 fprintf (f
, "UNKNOWN\n");
589 else if (type
== IPA_CONST
|| type
== IPA_CONST_REF
)
591 info_type
= jump_func
->value
.constant
;
592 fprintf (f
, "CONST : ");
593 print_generic_expr (f
, info_type
, 0);
596 else if (type
== IPA_PASS_THROUGH
)
598 fprintf (f
, "PASS THROUGH : ");
599 fprintf (f
, "%d\n", jump_func
->value
.formal_id
);
606 /* Print count scale data structures. */
608 ipcp_function_scale_print (FILE * f
)
610 struct cgraph_node
*node
;
612 for (node
= cgraph_nodes
; node
; node
= node
->next
)
616 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
617 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
618 " \n", (HOST_WIDE_INT
) ipcp_get_node_scale (node
));
622 /* Print counts of all cgraph nodes. */
624 ipcp_print_func_profile_counts (FILE * f
)
626 struct cgraph_node
*node
;
628 for (node
= cgraph_nodes
; node
; node
= node
->next
)
630 fprintf (f
, "function %s: ", cgraph_node_name (node
));
631 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
632 " \n", (HOST_WIDE_INT
) node
->count
);
636 /* Print counts of all cgraph edges. */
638 ipcp_print_call_profile_counts (FILE * f
)
640 struct cgraph_node
*node
;
641 struct cgraph_edge
*cs
;
643 for (node
= cgraph_nodes
; node
; node
= node
->next
)
645 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
647 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
648 cgraph_node_name (cs
->callee
));
649 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
650 (HOST_WIDE_INT
) cs
->count
);
655 /* Print all counts and probabilities of cfg edges of all functions. */
657 ipcp_print_edge_profiles (FILE * f
)
659 struct cgraph_node
*node
;
664 for (node
= cgraph_nodes
; node
; node
= node
->next
)
666 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
667 if (DECL_SAVED_TREE (node
->decl
))
670 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
671 fprintf (f
, "ENTRY: ");
672 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
673 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
676 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
679 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
681 fprintf (f
, "edge ENTRY -> EXIT, Count");
683 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
684 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
685 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
688 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
690 fprintf (f
, "bb[%d]: ", bb
->index
);
691 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
692 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
693 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
696 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
698 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
700 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
702 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
703 (HOST_WIDE_INT
) e
->count
, e
->probability
);
710 /* Print counts and frequencies for all basic blocks of all functions. */
712 ipcp_print_bb_profiles (FILE * f
)
715 struct cgraph_node
*node
;
717 for (node
= cgraph_nodes
; node
; node
= node
->next
)
719 fprintf (f
, "function %s: \n", cgraph_node_name (node
));
723 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
724 fprintf (f
, "ENTRY: Count");
725 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
726 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
729 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
731 fprintf (f
, "bb[%d]: Count", bb
->index
);
732 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
733 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
737 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
738 fprintf (f
, "EXIT: Count");
739 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
740 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
747 /* Print all IPCP data structures to F. */
749 ipcp_print_all_structures (FILE * f
)
751 ipcp_print_all_lattices (f
);
752 ipcp_function_scale_print (f
);
753 ipa_print_all_tree_maps (f
);
754 ipa_print_all_params_modified (f
);
755 ipcp_print_all_jump_functions (f
);
758 /* Print profile info for all functions. */
760 ipcp_print_profile_data (FILE * f
)
762 fprintf (f
, "\nNODE COUNTS :\n");
763 ipcp_print_func_profile_counts (f
);
764 fprintf (f
, "\nCS COUNTS stage:\n");
765 ipcp_print_call_profile_counts (f
);
766 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
767 ipcp_print_bb_profiles (f
);
768 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
769 ipcp_print_edge_profiles (f
);
772 /* Build and initialize ipa_replace_map struct according to LAT. This struct is
773 processed by versioning, which operates according to the flags set.
774 PARM_TREE is the formal parameter found to be constant. LAT represents the
776 static struct ipa_replace_map
*
777 ipcp_create_replace_map (struct function
*func
, tree parm_tree
,
778 struct ipcp_lattice
*lat
)
780 struct ipa_replace_map
*replace_map
;
783 replace_map
= XCNEW (struct ipa_replace_map
);
784 gcc_assert (ipcp_lat_is_const (lat
));
785 if (lat
->type
!= IPA_CONST_VALUE_REF
786 && is_gimple_reg (parm_tree
) && gimple_default_def (func
, parm_tree
)
787 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func
,
791 fprintf (dump_file
, "replacing param with const\n");
792 const_val
= build_const_val (lat
, TREE_TYPE (parm_tree
));
793 replace_map
->old_tree
=gimple_default_def (func
, parm_tree
);
794 replace_map
->new_tree
= const_val
;
795 replace_map
->replace_p
= true;
796 replace_map
->ref_p
= false;
800 replace_map
->old_tree
= NULL
;
801 replace_map
->new_tree
= NULL
;
802 replace_map
->replace_p
= false;
803 replace_map
->ref_p
= false;
809 /* Return true if this callsite should be redirected to the original callee
810 (instead of the cloned one). */
812 ipcp_need_redirect_p (struct cgraph_edge
*cs
)
814 struct ipa_node_params
*orig_callee_info
;
816 struct ipa_jump_func
*jump_func
;
818 orig_callee_info
= IPA_NODE_REF (ipcp_get_orig_node (cs
->callee
));
819 count
= ipa_get_param_count (orig_callee_info
);
820 for (i
= 0; i
< count
; i
++)
822 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (orig_callee_info
, i
);
823 if (ipcp_lat_is_const (lat
))
825 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
826 if (!ipcp_lat_is_const (lat
))
834 /* Fix the callsites and the call graph after function cloning was done. */
836 ipcp_update_callgraph (void)
838 struct cgraph_node
*node
, *orig_callee
;
839 struct cgraph_edge
*cs
;
841 for (node
= cgraph_nodes
; node
; node
= node
->next
)
843 /* want to fix only original nodes */
844 if (!node
->analyzed
|| ipcp_node_is_clone (node
))
846 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
847 if (ipcp_node_is_clone (cs
->callee
))
849 /* Callee is a cloned node */
850 orig_callee
= ipcp_get_orig_node (cs
->callee
);
851 if (ipcp_need_redirect_p (cs
))
853 cgraph_redirect_edge_callee (cs
, orig_callee
);
854 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (cs
->call_stmt
)),
862 /* Update all cfg basic blocks in NODE according to SCALE. */
864 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
868 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
869 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
872 /* Update all cfg edges in NODE according to SCALE. */
874 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
880 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
881 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
882 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
885 /* Update profiling info for versioned functions and the functions they were
888 ipcp_update_profiling (void)
890 struct cgraph_node
*node
, *orig_node
;
891 gcov_type scale
, scale_complement
;
892 struct cgraph_edge
*cs
;
894 for (node
= cgraph_nodes
; node
; node
= node
->next
)
896 if (ipcp_node_is_clone (node
))
898 orig_node
= ipcp_get_orig_node (node
);
899 scale
= ipcp_get_node_scale (orig_node
);
900 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
901 scale_complement
= REG_BR_PROB_BASE
- scale
;
903 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
904 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
905 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
906 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
907 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
908 ipcp_update_bb_counts (node
, scale
);
909 ipcp_update_bb_counts (orig_node
, scale_complement
);
910 ipcp_update_edges_counts (node
, scale
);
911 ipcp_update_edges_counts (orig_node
, scale_complement
);
916 /* Propagate the constant parameters found by ipcp_iterate_stage()
917 to the function's code. */
919 ipcp_insert_stage (void)
921 struct cgraph_node
*node
, *node1
= NULL
;
923 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
924 varray_type replace_trees
;
925 struct cgraph_edge
*cs
;
926 int node_callers
, count
;
928 struct ipa_replace_map
*replace_param
;
930 ipa_check_create_node_params ();
931 ipa_check_create_edge_args ();
933 for (node
= cgraph_nodes
; node
; node
= node
->next
)
935 struct ipa_node_params
*info
;
936 /* Propagation of the constant is forbidden in certain conditions. */
937 if (!node
->analyzed
|| ipcp_node_not_modifiable_p (node
))
939 info
= IPA_NODE_REF (node
);
940 if (ipa_is_called_with_var_arguments (info
))
943 count
= ipa_get_param_count (info
);
944 for (i
= 0; i
< count
; i
++)
946 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
947 if (ipcp_lat_is_const (lat
))
950 if (const_param
== 0)
952 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
953 for (i
= 0; i
< count
; i
++)
955 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
956 if (ipcp_lat_is_const (lat
))
958 parm_tree
= ipa_get_ith_param (info
, i
);
960 ipcp_create_replace_map (DECL_STRUCT_FUNCTION (node
->decl
),
962 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
965 /* Compute how many callers node has. */
967 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
969 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
970 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
971 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
972 /* Redirecting all the callers of the node to the
973 new versioned node. */
975 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
976 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
977 VARRAY_CLEAR (replace_trees
);
981 fprintf (dump_file
, "versioned function %s\n",
982 cgraph_node_name (node
));
983 ipcp_init_cloned_node (node
, node1
);
986 push_cfun (DECL_STRUCT_FUNCTION (node1
->decl
));
987 tree_register_cfg_hooks ();
988 current_function_decl
= node1
->decl
;
990 for (i
= 0; i
< count
; i
++)
992 struct ipcp_lattice
*lat
= ipcp_get_ith_lattice (info
, i
);
993 if (ipcp_lat_is_const (lat
))
995 parm_tree
= ipa_get_ith_param (info
, i
);
996 if (lat
->type
!= IPA_CONST_VALUE_REF
997 && !is_gimple_reg (parm_tree
))
998 ipcp_propagate_one_const (node1
, i
, lat
);
1001 if (gimple_in_ssa_p (cfun
))
1003 update_ssa (TODO_update_ssa
);
1004 #ifdef ENABLE_CHECKING
1008 free_dominance_info (CDI_DOMINATORS
);
1009 free_dominance_info (CDI_POST_DOMINATORS
);
1011 current_function_decl
= NULL
;
1014 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1016 ipcp_update_callgraph ();
1017 ipcp_update_profiling ();
1020 /* The IPCP driver. */
1025 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1026 ipa_check_create_node_params ();
1027 ipa_check_create_edge_args ();
1028 ipa_register_cgraph_hooks ();
1029 /* 1. Call the init stage to initialize
1030 the ipa_node_params and ipa_edge_args structures. */
1034 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1035 ipcp_print_all_structures (dump_file
);
1037 /* 2. Do the interprocedural propagation. */
1038 ipcp_iterate_stage ();
1041 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1042 ipcp_print_all_structures (dump_file
);
1043 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1044 ipcp_print_profile_data (dump_file
);
1046 /* 3. Insert the constants found to the functions. */
1047 ipcp_insert_stage ();
1050 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1051 ipcp_print_profile_data (dump_file
);
1053 /* Free all IPCP structures. */
1054 free_all_ipa_structures_after_ipa_cp ();
1056 fprintf (dump_file
, "\nIPA constant propagation end\n");
1057 cgraph_remove_unreachable_nodes (true, NULL
);
1061 /* Gate for IPCP optimization. */
1063 cgraph_gate_cp (void)
1068 struct simple_ipa_opt_pass pass_ipa_cp
=
1073 cgraph_gate_cp
, /* gate */
1074 ipcp_driver
, /* execute */
1077 0, /* static_pass_number */
1078 TV_IPA_CONSTANT_PROP
, /* tv_id */
1079 0, /* properties_required */
1080 PROP_trees
, /* properties_provided */
1081 0, /* properties_destroyed */
1082 0, /* todo_flags_start */
1083 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */