1 /* Interprocedural constant propagation
2 Copyright (C) 2005 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
22 /* Interprocedural constant propagation.
23 The aim of interprocedural constant propagation (IPCP) is to find which
24 function's argument has the same constant value in each invocation throughout
25 the whole program. For example, for an application consisting of two files,
48 printf ("value is %d",y);
51 The IPCP algorithm will find that g's formal argument y
52 is always called with the value 3.
54 The algorithm used is based on "Interprocedural Constant Propagation",
55 by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86,
58 The optimization is divided into three stages:
60 First stage - intraprocedural analysis
61 =======================================
62 This phase computes jump_function and modify information.
64 A jump function for a callsite represents the values passed as actual
66 of the callsite. There are three types of values :
67 Formal - the caller's formal parameter is passed as an actual argument.
68 Constant - a constant is passed as a an actual argument.
69 Unknown - neither of the above.
71 In order to compute the jump functions, we need the modify information for
72 the formal parameters of methods.
74 The jump function info, ipa_jump_func, is defined in ipa_edge
75 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
76 The modify info, ipa_modify, is defined in ipa_node structure
77 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
79 -ipcp_init_stage() is the first stage driver.
81 Second stage - interprocedural analysis
82 ========================================
83 This phase does the interprocedural constant propagation.
84 It computes for all formal parameters in the program
85 their cval value that may be:
87 BOTTOM - non constant.
88 CONSTANT_TYPE - constant value.
90 Cval of formal f will have a constant value if all callsites to this
91 function have the same constant value passed to f.
93 The cval info, ipcp_formal, is defined in ipa_node structure
94 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
96 -ipcp_iterate_stage() is the second stage driver.
98 Third phase - transformation of methods code
99 ============================================
100 Propagates the constant-valued formals into the function.
101 For each method mt, whose parameters are consts, we create a clone/version.
103 We use two ways to annotate the versioned function with the constant
105 1. We insert an assignment statement 'parameter = const' at the beginning
106 of the cloned method.
107 2. For read-only formals whose address is not taken, we replace all uses
108 of the formal with the constant (we provide versioning with an
109 ipa_replace_map struct representing the trees we want to replace).
111 We also need to modify some callsites to call to the cloned methods instead
112 of the original ones. For a callsite passing an argument found to be a
113 constant by IPCP, there are two different cases to handle:
114 1. A constant is passed as an argument.
115 2. A parameter (of the caller) passed as an argument (pass through argument).
117 In the first case, the callsite in the original caller should be redirected
118 to call the cloned callee.
119 In the second case, both the caller and the callee have clones
120 and the callsite of the cloned caller would be redirected to call to
123 The callgraph is updated accordingly.
125 This update is done in two stages:
126 First all cloned methods are created during a traversal of the callgraph,
127 during which all callsites are redirected to call the cloned method.
128 Then the callsites are traversed and updated as described above.
130 -ipcp_insert_stage() is the third phase driver.
136 #include "coretypes.h"
140 #include "ipa-prop.h"
141 #include "tree-flow.h"
142 #include "tree-pass.h"
145 #include "diagnostic.h"
147 /* Get orig node field of ipa_node associated with method MT. */
148 static inline struct cgraph_node
*
149 ipcp_method_orig_node (struct cgraph_node
*mt
)
151 return IPA_NODE_REF (mt
)->ipcp_orig_node
;
154 /* Return true if NODE is a cloned/versioned method. */
156 ipcp_method_is_cloned (struct cgraph_node
*node
)
158 return (ipcp_method_orig_node (node
) != NULL
);
161 /* Set ORIG_NODE in ipa_node associated with method NODE. */
163 ipcp_method_set_orig_node (struct cgraph_node
*node
,
164 struct cgraph_node
*orig_node
)
166 IPA_NODE_REF (node
)->ipcp_orig_node
= orig_node
;
169 /* Create ipa_node and its data structures for NEW_NODE.
170 Set ORIG_NODE as the orig_node field in ipa_node. */
172 ipcp_cloned_create (struct cgraph_node
*orig_node
,
173 struct cgraph_node
*new_node
)
175 ipa_node_create (new_node
);
176 ipcp_method_set_orig_node (new_node
, orig_node
);
177 ipa_method_formal_compute_count (new_node
);
178 ipa_method_compute_tree_map (new_node
);
181 /* Return cval_type field of CVAL. */
182 static inline enum cvalue_type
183 ipcp_cval_get_cvalue_type (struct ipcp_formal
*cval
)
185 return cval
->cval_type
;
188 /* Return scale for MT. */
189 static inline gcov_type
190 ipcp_method_get_scale (struct cgraph_node
*mt
)
192 return IPA_NODE_REF (mt
)->count_scale
;
195 /* Set COUNT as scale for MT. */
197 ipcp_method_set_scale (struct cgraph_node
*node
, gcov_type count
)
199 IPA_NODE_REF (node
)->count_scale
= count
;
202 /* Set TYPE as cval_type field of CVAL. */
204 ipcp_cval_set_cvalue_type (struct ipcp_formal
*cval
, enum cvalue_type type
)
206 cval
->cval_type
= type
;
209 /* Return cvalue field of CVAL. */
210 static inline union parameter_info
*
211 ipcp_cval_get_cvalue (struct ipcp_formal
*cval
)
213 return &(cval
->cvalue
);
216 /* Set VALUE as cvalue field CVAL. */
218 ipcp_cval_set_cvalue (struct ipcp_formal
*cval
, union parameter_info
*value
,
219 enum cvalue_type type
)
221 if (type
== CONST_VALUE
|| type
== CONST_VALUE_REF
)
222 cval
->cvalue
.value
= value
->value
;
225 /* Return whether TYPE is a constant type. */
227 ipcp_type_is_const (enum cvalue_type type
)
229 if (type
== CONST_VALUE
|| type
== CONST_VALUE_REF
)
235 /* Return true if CONST_VAL1 and CONST_VAL2 are equal. */
237 ipcp_cval_equal_cvalues (union parameter_info
*const_val1
,
238 union parameter_info
*const_val2
,
239 enum cvalue_type type1
, enum cvalue_type type2
)
241 gcc_assert (ipcp_type_is_const (type1
) && ipcp_type_is_const (type2
));
245 if (operand_equal_p (const_val1
->value
, const_val2
->value
, 0))
251 /* Compute Meet arithmetics:
252 Meet (BOTTOM, x) = BOTTOM
254 Meet (const_a,const_b) = BOTTOM, if const_a != const_b.
255 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
257 ipcp_cval_meet (struct ipcp_formal
*cval
, struct ipcp_formal
*cval1
,
258 struct ipcp_formal
*cval2
)
260 if (ipcp_cval_get_cvalue_type (cval1
) == BOTTOM
261 || ipcp_cval_get_cvalue_type (cval2
) == BOTTOM
)
263 ipcp_cval_set_cvalue_type (cval
, BOTTOM
);
266 if (ipcp_cval_get_cvalue_type (cval1
) == TOP
)
268 ipcp_cval_set_cvalue_type (cval
, ipcp_cval_get_cvalue_type (cval2
));
269 ipcp_cval_set_cvalue (cval
, ipcp_cval_get_cvalue (cval2
),
270 ipcp_cval_get_cvalue_type (cval2
));
273 if (ipcp_cval_get_cvalue_type (cval2
) == TOP
)
275 ipcp_cval_set_cvalue_type (cval
, ipcp_cval_get_cvalue_type (cval1
));
276 ipcp_cval_set_cvalue (cval
, ipcp_cval_get_cvalue (cval1
),
277 ipcp_cval_get_cvalue_type (cval1
));
280 if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1
),
281 ipcp_cval_get_cvalue (cval2
),
282 ipcp_cval_get_cvalue_type (cval1
),
283 ipcp_cval_get_cvalue_type (cval2
)))
285 ipcp_cval_set_cvalue_type (cval
, BOTTOM
);
288 ipcp_cval_set_cvalue_type (cval
, ipcp_cval_get_cvalue_type (cval1
));
289 ipcp_cval_set_cvalue (cval
, ipcp_cval_get_cvalue (cval1
),
290 ipcp_cval_get_cvalue_type (cval1
));
293 /* Return cval structure for the formal at index INFO_TYPE in MT. */
294 static inline struct ipcp_formal
*
295 ipcp_method_cval (struct cgraph_node
*mt
, int info_type
)
297 return &(IPA_NODE_REF (mt
)->ipcp_cval
[info_type
]);
300 /* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL.
301 If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is
304 ipcp_cval_compute (struct ipcp_formal
*cval
, struct cgraph_node
*mt
,
305 enum jump_func_type type
, union parameter_info
*info_type
)
307 if (type
== UNKNOWN_IPATYPE
)
308 ipcp_cval_set_cvalue_type (cval
, BOTTOM
);
309 else if (type
== CONST_IPATYPE
)
311 ipcp_cval_set_cvalue_type (cval
, CONST_VALUE
);
312 ipcp_cval_set_cvalue (cval
, info_type
, CONST_VALUE
);
314 else if (type
== CONST_IPATYPE_REF
)
316 ipcp_cval_set_cvalue_type (cval
, CONST_VALUE_REF
);
317 ipcp_cval_set_cvalue (cval
, info_type
, CONST_VALUE_REF
);
319 else if (type
== FORMAL_IPATYPE
)
321 enum cvalue_type type
=
322 ipcp_cval_get_cvalue_type (ipcp_method_cval
323 (mt
, info_type
->formal_id
));
324 ipcp_cval_set_cvalue_type (cval
, type
);
325 ipcp_cval_set_cvalue (cval
,
326 ipcp_cval_get_cvalue (ipcp_method_cval
327 (mt
, info_type
->formal_id
)),
332 /* True when CVAL1 and CVAL2 values are not the same. */
334 ipcp_cval_changed (struct ipcp_formal
*cval1
, struct ipcp_formal
*cval2
)
336 if (ipcp_cval_get_cvalue_type (cval1
) == ipcp_cval_get_cvalue_type (cval2
))
338 if (ipcp_cval_get_cvalue_type (cval1
) != CONST_VALUE
&&
339 ipcp_cval_get_cvalue_type (cval1
) != CONST_VALUE_REF
)
341 if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1
),
342 ipcp_cval_get_cvalue (cval2
),
343 ipcp_cval_get_cvalue_type (cval1
),
344 ipcp_cval_get_cvalue_type (cval2
)))
350 /* Create cval structure for method MT. */
352 ipcp_formal_create (struct cgraph_node
*mt
)
354 IPA_NODE_REF (mt
)->ipcp_cval
=
355 xcalloc (ipa_method_formal_count (mt
), sizeof (struct ipcp_formal
));
358 /* Set cval structure of I-th formal of MT to CVAL. */
360 ipcp_method_cval_set (struct cgraph_node
*mt
, int i
, struct ipcp_formal
*cval
)
362 IPA_NODE_REF (mt
)->ipcp_cval
[i
].cval_type
= cval
->cval_type
;
363 ipcp_cval_set_cvalue (ipcp_method_cval (mt
, i
),
364 ipcp_cval_get_cvalue (cval
), cval
->cval_type
);
367 /* Set type of cval structure of formal I of MT to CVAL_TYPE1. */
369 ipcp_method_cval_set_cvalue_type (struct cgraph_node
*mt
, int i
,
370 enum cvalue_type cval_type1
)
372 IPA_NODE_REF (mt
)->ipcp_cval
[i
].cval_type
= cval_type1
;
375 /* Print ipcp_cval data structures to F. */
377 ipcp_method_cval_print (FILE * f
)
379 struct cgraph_node
*node
;
383 fprintf (f
, "\nCVAL PRINT\n");
384 for (node
= cgraph_nodes
; node
; node
= node
->next
)
386 fprintf (f
, "Printing cvals %s:\n", cgraph_node_name (node
));
387 count
= ipa_method_formal_count (node
);
388 for (i
= 0; i
< count
; i
++)
390 if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
))
392 || ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
)) ==
395 fprintf (f
, " param [%d]: ", i
);
396 fprintf (f
, "type is CONST ");
398 ipcp_cval_get_cvalue (ipcp_method_cval (node
, i
))->
400 print_generic_expr (f
, cvalue
, 0);
403 else if (ipcp_method_cval (node
, i
)->cval_type
== TOP
)
404 fprintf (f
, "param [%d]: type is TOP \n", i
);
406 fprintf (f
, "param [%d]: type is BOTTOM \n", i
);
411 /* Initialize ipcp_cval array of MT with TOP values.
412 All cvals for a method's formal parameters are initialized to BOTTOM
413 The currently supported types are integer types, real types and
414 Fortran constants (i.e. references to constants defined as
415 const_decls). All other types are not analyzed and therefore are
416 assigned with BOTTOM. */
418 ipcp_method_cval_init (struct cgraph_node
*mt
)
423 ipcp_formal_create (mt
);
424 for (i
= 0; i
< ipa_method_formal_count (mt
); i
++)
426 parm_tree
= ipa_method_get_tree (mt
, i
);
427 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree
))
428 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree
))
429 || POINTER_TYPE_P (TREE_TYPE (parm_tree
)))
430 ipcp_method_cval_set_cvalue_type (mt
, i
, TOP
);
432 ipcp_method_cval_set_cvalue_type (mt
, i
, BOTTOM
);
436 /* Create a new assignment statment and make
437 it the first statement in the function FN
439 PARM1 is the lhs of the assignment and
442 constant_val_insert (tree fn
, tree parm1
, tree val
)
444 struct function
*func
;
449 init_stmt
= build2 (MODIFY_EXPR
, void_type_node
, parm1
, val
);
450 func
= DECL_STRUCT_FUNCTION (fn
);
452 current_function_decl
= fn
;
453 if (ENTRY_BLOCK_PTR_FOR_FUNCTION (func
)->succs
)
454 FOR_EACH_EDGE (e_step
, ei
, ENTRY_BLOCK_PTR_FOR_FUNCTION (func
)->succs
)
455 bsi_insert_on_edge_immediate (e_step
, init_stmt
);
458 /* build INTEGER_CST tree with type TREE_TYPE and
459 value according to CVALUE. Return the tree. */
461 build_const_val (union parameter_info
*cvalue
, enum cvalue_type type
,
464 tree const_val
= NULL
;
466 gcc_assert (ipcp_type_is_const (type
));
467 const_val
= fold_convert (tree_type
, cvalue
->value
);
471 /* Build the tree representing the constant and call
472 constant_val_insert(). */
474 ipcp_propagate_const (struct cgraph_node
*mt
, int param
,
475 union parameter_info
*cvalue
,enum cvalue_type type
)
482 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (mt
));
484 parm_tree
= ipa_method_get_tree (mt
, param
);
485 const_val
= build_const_val (cvalue
, type
, TREE_TYPE (parm_tree
));
486 constant_val_insert (fndecl
, parm_tree
, const_val
);
489 /* Compute the proper scale for NODE. It is the ratio between
490 the number of direct calls (represented on the incoming
491 cgraph_edges) and sum of all invocations of NODE (represented
492 as count in cgraph_node). */
494 ipcp_method_compute_scale (struct cgraph_node
*node
)
497 struct cgraph_edge
*cs
;
500 /* Compute sum of all counts of callers. */
501 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
503 if (node
->count
== 0)
504 ipcp_method_set_scale (node
, 0);
506 ipcp_method_set_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
509 /* Initialization and computation of IPCP data structures.
510 It is an intraprocedural
511 analysis of methods, which gathers information to be propagated
514 ipcp_init_stage (void)
516 struct cgraph_node
*node
;
517 struct cgraph_edge
*cs
;
519 for (node
= cgraph_nodes
; node
; node
= node
->next
)
521 ipa_method_formal_compute_count (node
);
522 ipa_method_compute_tree_map (node
);
523 ipcp_method_cval_init (node
);
524 ipa_method_compute_modify (node
);
525 ipcp_method_compute_scale (node
);
527 for (node
= cgraph_nodes
; node
; node
= node
->next
)
529 /* building jump functions */
530 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
532 ipa_callsite_compute_count (cs
);
533 if (ipa_callsite_param_count (cs
)
534 != ipa_method_formal_count (cs
->callee
))
536 /* Handle cases of functions with
537 a variable number of parameters. */
538 ipa_callsite_param_count_set (cs
, 0);
539 ipa_method_formal_count_set (cs
->callee
, 0);
542 ipa_callsite_compute_param (cs
);
547 /* Return true if there are some formal parameters whose value is TOP.
548 Change their values to BOTTOM, since they weren't determined. */
550 ipcp_after_propagate (void)
553 struct cgraph_node
*node
;
557 for (node
= cgraph_nodes
; node
; node
= node
->next
)
559 count
= ipa_method_formal_count (node
);
560 for (i
= 0; i
< count
; i
++)
561 if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
)) == TOP
)
564 ipcp_method_cval_set_cvalue_type (node
, i
, BOTTOM
);
570 /* Interprocedural analysis. The algorithm propagates constants from
571 the caller's parameters to the callee's arguments. */
573 ipcp_propagate_stage (void)
576 struct ipcp_formal cval1
= { 0, {0} }, cval
= { 0,{0} };
577 struct ipcp_formal
*cval2
;
578 struct cgraph_node
*mt
, *callee
;
579 struct cgraph_edge
*cs
;
580 struct ipa_jump_func
*jump_func
;
581 enum jump_func_type type
;
582 union parameter_info
*info_type
;
586 /* Initialize worklist to contain all methods. */
587 wl
= ipa_methodlist_init ();
588 while (ipa_methodlist_not_empty (wl
))
590 mt
= ipa_remove_method (&wl
);
591 for (cs
= mt
->callees
; cs
; cs
= cs
->next_callee
)
593 callee
= ipa_callsite_callee (cs
);
594 count
= ipa_callsite_param_count (cs
);
595 for (i
= 0; i
< count
; i
++)
597 jump_func
= ipa_callsite_param (cs
, i
);
598 type
= get_type (jump_func
);
599 info_type
= ipa_jf_get_info_type (jump_func
);
600 ipcp_cval_compute (&cval1
, mt
, type
, info_type
);
601 cval2
= ipcp_method_cval (callee
, i
);
602 ipcp_cval_meet (&cval
, &cval1
, cval2
);
603 if (ipcp_cval_changed (&cval
, cval2
))
605 ipcp_method_cval_set (callee
, i
, &cval
);
606 ipa_add_method (&wl
, callee
);
613 /* Call the constant propagation algorithm and re-call it if necessary
614 (if there are undetermined values left). */
616 ipcp_iterate_stage (void)
618 ipcp_propagate_stage ();
619 if (ipcp_after_propagate ())
620 /* Some cvals have changed from TOP to BOTTOM.
621 This change should be propagated. */
622 ipcp_propagate_stage ();
625 /* Check conditions to forbid constant insertion to MT. */
627 ipcp_method_dont_insert_const (struct cgraph_node
*mt
)
629 /* ??? Handle pending sizes case. */
630 if (DECL_UNINLINABLE (mt
->decl
))
635 /* Print ipa_jump_func data structures to F. */
637 ipcp_callsite_param_print (FILE * f
)
639 struct cgraph_node
*node
;
641 struct cgraph_edge
*cs
;
642 struct ipa_jump_func
*jump_func
;
643 enum jump_func_type type
;
646 fprintf (f
, "\nCALLSITE PARAM PRINT\n");
647 for (node
= cgraph_nodes
; node
; node
= node
->next
)
649 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
651 fprintf (f
, "callsite %s ", cgraph_node_name (node
));
652 fprintf (f
, "-> %s :: \n", cgraph_node_name (cs
->callee
));
653 count
= ipa_callsite_param_count (cs
);
654 for (i
= 0; i
< count
; i
++)
656 jump_func
= ipa_callsite_param (cs
, i
);
657 type
= get_type (jump_func
);
659 fprintf (f
, " param %d: ", i
);
660 if (type
== UNKNOWN_IPATYPE
)
661 fprintf (f
, "UNKNOWN\n");
662 else if (type
== CONST_IPATYPE
|| type
== CONST_IPATYPE_REF
)
665 ipa_jf_get_info_type (jump_func
)->value
;
666 fprintf (f
, "CONST : ");
667 print_generic_expr (f
, info_type
, 0);
670 else if (type
== FORMAL_IPATYPE
)
672 fprintf (f
, "FORMAL : ");
674 ipa_jf_get_info_type (jump_func
)->formal_id
);
681 /* Print count scale data structures. */
683 ipcp_method_scale_print (FILE * f
)
685 struct cgraph_node
*node
;
687 for (node
= cgraph_nodes
; node
; node
= node
->next
)
689 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
690 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
691 " \n", (HOST_WIDE_INT
) ipcp_method_get_scale (node
));
695 /* Print counts of all cgraph nodes. */
697 ipcp_profile_mt_count_print (FILE * f
)
699 struct cgraph_node
*node
;
701 for (node
= cgraph_nodes
; node
; node
= node
->next
)
703 fprintf (f
, "method %s: ", cgraph_node_name (node
));
704 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
705 " \n", (HOST_WIDE_INT
) node
->count
);
709 /* Print counts of all cgraph edges. */
711 ipcp_profile_cs_count_print (FILE * f
)
713 struct cgraph_node
*node
;
714 struct cgraph_edge
*cs
;
716 for (node
= cgraph_nodes
; node
; node
= node
->next
)
718 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
720 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
721 cgraph_node_name (cs
->callee
));
722 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
723 (HOST_WIDE_INT
) cs
->count
);
728 /* Print all counts and probabilities of cfg edges of all methods. */
730 ipcp_profile_edge_print (FILE * f
)
732 struct cgraph_node
*node
;
737 for (node
= cgraph_nodes
; node
; node
= node
->next
)
739 fprintf (f
, "method %s: \n", cgraph_node_name (node
));
740 if (DECL_SAVED_TREE (node
->decl
))
743 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
744 fprintf (f
, "ENTRY: ");
745 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
746 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
749 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
752 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
754 fprintf (f
, "edge ENTRY -> EXIT, Count");
756 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
757 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
758 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
761 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
763 fprintf (f
, "bb[%d]: ", bb
->index
);
764 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
765 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
766 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
769 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
771 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
773 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
775 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
776 (HOST_WIDE_INT
) e
->count
, e
->probability
);
783 /* Print counts and frequencies for all basic blocks of all methods. */
785 ipcp_profile_bb_print (FILE * f
)
788 struct cgraph_node
*node
;
790 for (node
= cgraph_nodes
; node
; node
= node
->next
)
792 fprintf (f
, "method %s: \n", cgraph_node_name (node
));
793 if (DECL_SAVED_TREE (node
->decl
))
796 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
797 fprintf (f
, "ENTRY: Count");
798 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
799 " Frquency %d\n", (HOST_WIDE_INT
) bb
->count
,
802 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
804 fprintf (f
, "bb[%d]: Count", bb
->index
);
805 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
806 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
810 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
811 fprintf (f
, "EXIT: Count");
812 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
813 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
820 /* Print all IPCP data structures to F. */
822 ipcp_structures_print (FILE * f
)
824 ipcp_method_cval_print (f
);
825 ipcp_method_scale_print (f
);
826 ipa_method_tree_print (f
);
827 ipa_method_modify_print (f
);
828 ipcp_callsite_param_print (f
);
831 /* Print profile info for all methods. */
833 ipcp_profile_print (FILE * f
)
835 fprintf (f
, "\nNODE COUNTS :\n");
836 ipcp_profile_mt_count_print (f
);
837 fprintf (f
, "\nCS COUNTS stage:\n");
838 ipcp_profile_cs_count_print (f
);
839 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
840 ipcp_profile_bb_print (f
);
841 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
842 ipcp_profile_edge_print (f
);
845 /* Build and initialize ipa_replace_map struct
846 according to TYPE. This struct is read by versioning, which
847 operates according to the flags sent. PARM_TREE is the
848 formal's tree found to be constant. CVALUE represents the constant. */
849 static struct ipa_replace_map
*
850 ipcp_replace_map_create (enum cvalue_type type
, tree parm_tree
,
851 union parameter_info
*cvalue
)
853 struct ipa_replace_map
*replace_map
;
856 replace_map
= xcalloc (1, sizeof (struct ipa_replace_map
));
857 gcc_assert (ipcp_type_is_const (type
));
858 if (type
== CONST_VALUE_REF
)
861 build_const_val (cvalue
, type
, TREE_TYPE (TREE_TYPE (parm_tree
)));
862 replace_map
->old_tree
= parm_tree
;
863 replace_map
->new_tree
= const_val
;
864 replace_map
->replace_p
= true;
865 replace_map
->ref_p
= true;
867 else if (TREE_READONLY (parm_tree
) && !TREE_ADDRESSABLE (parm_tree
))
869 const_val
= build_const_val (cvalue
, type
, TREE_TYPE (parm_tree
));
870 replace_map
->old_tree
= parm_tree
;
871 replace_map
->new_tree
= const_val
;
872 replace_map
->replace_p
= true;
873 replace_map
->ref_p
= false;
877 replace_map
->old_tree
= NULL
;
878 replace_map
->new_tree
= NULL
;
879 replace_map
->replace_p
= false;
880 replace_map
->ref_p
= false;
886 /* Return true if this callsite should be redirected to
887 the orig callee (instead of the cloned one). */
889 ipcp_redirect (struct cgraph_edge
*cs
)
891 struct cgraph_node
*caller
, *callee
, *orig_callee
;
893 struct ipa_jump_func
*jump_func
;
894 enum jump_func_type type
;
895 enum cvalue_type cval_type
;
899 orig_callee
= ipcp_method_orig_node (callee
);
900 count
= ipa_method_formal_count (orig_callee
);
901 for (i
= 0; i
< count
; i
++)
904 ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee
, i
));
905 if (ipcp_type_is_const (cval_type
))
907 jump_func
= ipa_callsite_param (cs
, i
);
908 type
= get_type (jump_func
);
909 if (type
!= CONST_IPATYPE
910 && type
!= CONST_IPATYPE_REF
)
918 /* Fix the callsites and the callgraph after function cloning was done. */
920 ipcp_update_callgraph (void)
922 struct cgraph_node
*node
, *orig_callee
;
923 struct cgraph_edge
*cs
;
925 for (node
= cgraph_nodes
; node
; node
= node
->next
)
927 /* want to fix only original nodes */
928 if (ipcp_method_is_cloned (node
))
930 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
931 if (ipcp_method_is_cloned (cs
->callee
))
933 /* Callee is a cloned node */
934 orig_callee
= ipcp_method_orig_node (cs
->callee
);
935 if (ipcp_redirect (cs
))
937 cgraph_redirect_edge_callee (cs
, orig_callee
);
938 TREE_OPERAND (TREE_OPERAND
939 (get_call_expr_in (cs
->call_stmt
), 0), 0) =
946 /* Update all cfg basic blocks in NODE according to SCALE. */
948 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
952 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
953 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
956 /* Update all cfg edges in NODE according to SCALE. */
958 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
964 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
965 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
966 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
969 /* Update profiling info for versioned methods and the
970 methods they were versioned from. */
972 ipcp_update_profiling (void)
974 struct cgraph_node
*node
, *orig_node
;
975 gcov_type scale
, scale_complement
;
976 struct cgraph_edge
*cs
;
978 for (node
= cgraph_nodes
; node
; node
= node
->next
)
980 if (ipcp_method_is_cloned (node
))
982 orig_node
= ipcp_method_orig_node (node
);
983 scale
= ipcp_method_get_scale (orig_node
);
984 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
985 scale_complement
= REG_BR_PROB_BASE
- scale
;
987 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
988 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
989 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
990 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
991 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
992 ipcp_update_bb_counts (node
, scale
);
993 ipcp_update_bb_counts (orig_node
, scale_complement
);
994 ipcp_update_edges_counts (node
, scale
);
995 ipcp_update_edges_counts (orig_node
, scale_complement
);
1000 /* Propagate the constant parameters found by ipcp_iterate_stage()
1001 to the function's code. */
1003 ipcp_insert_stage (void)
1005 struct cgraph_node
*node
, *node1
= NULL
;
1007 union parameter_info
*cvalue
;
1008 varray_type redirect_callers
, replace_trees
;
1009 struct cgraph_edge
*cs
;
1010 int node_callers
, count
;
1012 enum cvalue_type type
;
1013 struct ipa_replace_map
*replace_param
;
1015 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1017 /* Propagation of the constant is forbidden in
1018 certain conditions. */
1019 if (ipcp_method_dont_insert_const (node
))
1022 count
= ipa_method_formal_count (node
);
1023 for (i
= 0; i
< count
; i
++)
1025 type
= ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
));
1026 if (ipcp_type_is_const (type
))
1029 if (const_param
== 0)
1031 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
1032 for (i
= 0; i
< count
; i
++)
1034 type
= ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
));
1035 if (ipcp_type_is_const (type
))
1037 cvalue
= ipcp_cval_get_cvalue (ipcp_method_cval (node
, i
));
1038 parm_tree
= ipa_method_get_tree (node
, i
);
1040 ipcp_replace_map_create (type
, parm_tree
, cvalue
);
1041 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
1044 /* Compute how many callers node has. */
1046 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1048 VARRAY_GENERIC_PTR_INIT (redirect_callers
, node_callers
,
1049 "redirect_callers");
1050 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1051 VARRAY_PUSH_GENERIC_PTR (redirect_callers
, cs
);
1052 /* Redirecting all the callers of the node to the
1053 new versioned node. */
1055 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
1056 VARRAY_CLEAR (redirect_callers
);
1057 VARRAY_CLEAR (replace_trees
);
1061 fprintf (dump_file
, "versioned function %s\n",
1062 cgraph_node_name (node
));
1063 ipcp_cloned_create (node
, node1
);
1064 for (i
= 0; i
< count
; i
++)
1066 type
= ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
));
1067 if (ipcp_type_is_const (type
))
1069 cvalue
= ipcp_cval_get_cvalue (ipcp_method_cval (node
, i
));
1070 parm_tree
= ipa_method_get_tree (node
, i
);
1071 if (type
!= CONST_VALUE_REF
1072 && !TREE_READONLY (parm_tree
))
1073 ipcp_propagate_const (node1
, i
, cvalue
, type
);
1077 ipcp_update_callgraph ();
1078 ipcp_update_profiling ();
1081 /* The IPCP driver. */
1086 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1087 ipa_nodes_create ();
1088 ipa_edges_create ();
1089 /* 1. Call the init stage to initialize
1090 the ipa_node and ipa_edge structures. */
1094 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1095 ipcp_structures_print (dump_file
);
1097 /* 2. Do the interprocedural propagation. */
1098 ipcp_iterate_stage ();
1101 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1102 ipcp_structures_print (dump_file
);
1103 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1104 ipcp_profile_print (dump_file
);
1106 /* 3. Insert the constants found to the functions. */
1107 ipcp_insert_stage ();
1110 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1111 ipcp_profile_print (dump_file
);
1113 /* Free all IPCP structures. */
1118 fprintf (dump_file
, "\nIPA constant propagation end\n");
1119 cgraph_remove_unreachable_nodes (true, NULL
);
1122 /* Gate for IPCP optimization. */
1124 cgraph_gate_cp (void)
1129 struct tree_opt_pass pass_ipa_cp
= {
1131 cgraph_gate_cp
, /* gate */
1132 ipcp_driver
, /* execute */
1135 0, /* static_pass_number */
1136 TV_IPA_CONSTANT_PROP
, /* tv_id */
1137 0, /* properties_required */
1138 PROP_trees
, /* properties_provided */
1139 0, /* properties_destroyed */
1140 0, /* todo_flags_start */
1141 TODO_dump_cgraph
| TODO_dump_func
, /* todo_flags_finish */