1 /* Interprocedural constant propagation
2 Copyright (C) 2005, 2006, 2007 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.
22 The aim of interprocedural constant propagation (IPCP) is to find which
23 function's argument has the same constant value in each invocation throughout
24 the whole program. For example, for an application consisting of two files,
47 printf ("value is %d",y);
50 The IPCP algorithm will find that g's formal argument y
51 is always called with the value 3.
53 The algorithm used is based on "Interprocedural Constant Propagation",
54 by Challahan David, Keith D Cooper, Ken Kennedy, Linda Torczon, Comp86,
57 The optimization is divided into three stages:
59 First stage - intraprocedural analysis
60 =======================================
61 This phase computes jump_function and modify information.
63 A jump function for a callsite represents the values passed as actual
65 of the callsite. There are three types of values :
66 Formal - the caller's formal parameter is passed as an actual argument.
67 Constant - a constant is passed as an actual argument.
68 Unknown - neither of the above.
70 In order to compute the jump functions, we need the modify information for
71 the formal parameters of methods.
73 The jump function info, ipa_jump_func, is defined in ipa_edge
74 structure (defined in ipa_prop.h and pointed to by cgraph_node->aux)
75 The modify info, modified_flags, is defined in ipa_node_params structure
76 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
78 -ipcp_init_stage() is the first stage driver.
80 Second stage - interprocedural analysis
81 ========================================
82 This phase does the interprocedural constant propagation.
83 It computes for all formal parameters in the program
84 their cval value that may be:
86 BOTTOM - non constant.
87 CONSTANT_TYPE - constant value.
89 Cval of formal f will have a constant value if all callsites to this
90 function have the same constant value passed to f.
92 The cval info, ipcp_lattice, is defined in ipa_node_params structure
93 (defined in ipa_prop.h and pointed to by cgraph_edge->aux).
95 -ipcp_iterate_stage() is the second stage driver.
97 Third phase - transformation of methods code
98 ============================================
99 Propagates the constant-valued formals into the function.
100 For each method mt, whose parameters are consts, we create a clone/version.
102 We use two ways to annotate the versioned function with the constant
104 1. We insert an assignment statement 'parameter = const' at the beginning
105 of the cloned method.
106 2. For read-only formals whose address is not taken, we replace all uses
107 of the formal with the constant (we provide versioning with an
108 ipa_replace_map struct representing the trees we want to replace).
110 We also need to modify some callsites to call to the cloned methods instead
111 of the original ones. For a callsite passing an argument found to be a
112 constant by IPCP, there are two different cases to handle:
113 1. A constant is passed as an argument.
114 2. A parameter (of the caller) passed as an argument (pass through argument).
116 In the first case, the callsite in the original caller should be redirected
117 to call the cloned callee.
118 In the second case, both the caller and the callee have clones
119 and the callsite of the cloned caller would be redirected to call to
122 The callgraph is updated accordingly.
124 This update is done in two stages:
125 First all cloned methods are created during a traversal of the callgraph,
126 during which all callsites are redirected to call the cloned method.
127 Then the callsites are traversed and updated as described above.
129 -ipcp_insert_stage() is the third phase driver.
135 #include "coretypes.h"
139 #include "ipa-prop.h"
140 #include "tree-flow.h"
141 #include "tree-pass.h"
144 #include "diagnostic.h"
145 #include "tree-dump.h"
146 #include "tree-inline.h"
148 /* Get orig node field of ipa_node_params associated with method MT. */
149 static inline struct cgraph_node
*
150 ipcp_method_orig_node (struct cgraph_node
*mt
)
152 return IPA_NODE_REF (mt
)->ipcp_orig_node
;
155 /* Return true if NODE is a cloned/versioned method. */
157 ipcp_method_is_cloned (struct cgraph_node
*node
)
159 return (ipcp_method_orig_node (node
) != NULL
);
162 /* Set ORIG_NODE in ipa_node associated with method NODE. */
164 ipcp_method_set_orig_node (struct cgraph_node
*node
,
165 struct cgraph_node
*orig_node
)
167 IPA_NODE_REF (node
)->ipcp_orig_node
= orig_node
;
170 /* Create ipa_node and its data structures for NEW_NODE.
171 Set ORIG_NODE as the orig_node field in ipa_node. */
173 ipcp_cloned_create (struct cgraph_node
*orig_node
,
174 struct cgraph_node
*new_node
)
176 ipa_create_node_params (new_node
);
177 ipcp_method_set_orig_node (new_node
, orig_node
);
178 ipa_count_formal_params (new_node
);
179 ipa_create_param_decls_array (new_node
);
182 /* Return cval_type field of CVAL. */
183 static inline enum ipa_lattice_type
184 ipcp_cval_get_cvalue_type (struct ipcp_lattice
*cval
)
189 /* Return scale for MT. */
190 static inline gcov_type
191 ipcp_method_get_scale (struct cgraph_node
*mt
)
193 return IPA_NODE_REF (mt
)->count_scale
;
196 /* Set COUNT as scale for MT. */
198 ipcp_method_set_scale (struct cgraph_node
*node
, gcov_type count
)
200 IPA_NODE_REF (node
)->count_scale
= count
;
203 /* Set TYPE as cval_type field of CVAL. */
205 ipcp_cval_set_cvalue_type (struct ipcp_lattice
*cval
, enum jump_func_type type
)
210 /* Return cvalue field of CVAL. */
212 ipcp_cval_get_cvalue (struct ipcp_lattice
*cval
)
214 return cval
->constant
;
217 /* Set VALUE as cvalue field CVAL. */
219 ipcp_cval_set_cvalue (struct ipcp_lattice
*cval
, tree value
,
220 enum ipa_lattice_type type
)
222 if (type
== IPA_CONST_VALUE
|| type
== IPA_CONST_VALUE_REF
)
223 cval
->constant
= value
;
226 /* Return whether TYPE is a constant type. */
228 ipcp_type_is_const (enum ipa_lattice_type type
)
230 if (type
== IPA_CONST_VALUE
|| type
== IPA_CONST_VALUE_REF
)
236 /* Return true if CONST_VAL1 and CONST_VAL2 are equal. */
238 ipcp_cval_equal_cvalues (tree const_val1
, tree const_val2
,
239 enum ipa_lattice_type type1
,
240 enum ipa_lattice_type type2
)
242 gcc_assert (ipcp_type_is_const (type1
) && ipcp_type_is_const (type2
));
246 if (operand_equal_p (const_val1
, const_val2
, 0))
252 /* Compute Meet arithmetics:
253 Meet (IPA_BOTTOM, x) = IPA_BOTTOM
255 Meet (const_a,const_b) = IPA_BOTTOM, if const_a != const_b.
256 MEET (const_a,const_b) = const_a, if const_a == const_b.*/
258 ipcp_cval_meet (struct ipcp_lattice
*cval
, struct ipcp_lattice
*cval1
,
259 struct ipcp_lattice
*cval2
)
261 if (ipcp_cval_get_cvalue_type (cval1
) == IPA_BOTTOM
262 || ipcp_cval_get_cvalue_type (cval2
) == IPA_BOTTOM
)
264 ipcp_cval_set_cvalue_type (cval
, IPA_BOTTOM
);
267 if (ipcp_cval_get_cvalue_type (cval1
) == IPA_TOP
)
269 ipcp_cval_set_cvalue_type (cval
, ipcp_cval_get_cvalue_type (cval2
));
270 ipcp_cval_set_cvalue (cval
, ipcp_cval_get_cvalue (cval2
),
271 ipcp_cval_get_cvalue_type (cval2
));
274 if (ipcp_cval_get_cvalue_type (cval2
) == IPA_TOP
)
276 ipcp_cval_set_cvalue_type (cval
, ipcp_cval_get_cvalue_type (cval1
));
277 ipcp_cval_set_cvalue (cval
, ipcp_cval_get_cvalue (cval1
),
278 ipcp_cval_get_cvalue_type (cval1
));
281 if (!ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1
),
282 ipcp_cval_get_cvalue (cval2
),
283 ipcp_cval_get_cvalue_type (cval1
),
284 ipcp_cval_get_cvalue_type (cval2
)))
286 ipcp_cval_set_cvalue_type (cval
, IPA_BOTTOM
);
289 ipcp_cval_set_cvalue_type (cval
, ipcp_cval_get_cvalue_type (cval1
));
290 ipcp_cval_set_cvalue (cval
, ipcp_cval_get_cvalue (cval1
),
291 ipcp_cval_get_cvalue_type (cval1
));
294 /* Return cval structure for the formal at index INFO_TYPE in MT. */
295 static inline struct ipcp_lattice
*
296 ipcp_method_cval (struct cgraph_node
*mt
, int info_type
)
298 return &(IPA_NODE_REF (mt
)->ipcp_lattices
[info_type
]);
301 /* Given the jump function (TYPE, INFO_TYPE), compute a new value of CVAL.
302 If TYPE is FORMAL_IPA_TYPE, the cval of the corresponding formal is
305 ipcp_cval_compute (struct ipcp_lattice
*cval
, struct cgraph_node
*mt
,
306 enum jump_func_type type
,
307 union jump_func_value
*info_type
)
309 if (type
== IPA_UNKNOWN
)
310 ipcp_cval_set_cvalue_type (cval
, IPA_BOTTOM
);
311 else if (type
== IPA_CONST
)
313 ipcp_cval_set_cvalue_type (cval
, IPA_CONST_VALUE
);
314 ipcp_cval_set_cvalue (cval
, info_type
->constant
, IPA_CONST_VALUE
);
316 else if (type
== IPA_CONST_REF
)
318 ipcp_cval_set_cvalue_type (cval
, IPA_CONST_VALUE_REF
);
319 ipcp_cval_set_cvalue (cval
, info_type
->constant
, IPA_CONST_VALUE_REF
);
321 else if (type
== IPA_PASS_THROUGH
)
323 enum ipa_lattice_type type
=
324 ipcp_cval_get_cvalue_type (ipcp_method_cval
325 (mt
, info_type
->formal_id
));
326 ipcp_cval_set_cvalue_type (cval
, type
);
327 ipcp_cval_set_cvalue (cval
,
328 ipcp_cval_get_cvalue (ipcp_method_cval
329 (mt
, info_type
->formal_id
)),
334 /* True when CVAL1 and CVAL2 values are not the same. */
336 ipcp_cval_changed (struct ipcp_lattice
*cval1
, struct ipcp_lattice
*cval2
)
338 if (ipcp_cval_get_cvalue_type (cval1
) == ipcp_cval_get_cvalue_type (cval2
))
340 if (ipcp_cval_get_cvalue_type (cval1
) != IPA_CONST_VALUE
341 && ipcp_cval_get_cvalue_type (cval1
) != IPA_CONST_VALUE_REF
)
343 if (ipcp_cval_equal_cvalues (ipcp_cval_get_cvalue (cval1
),
344 ipcp_cval_get_cvalue (cval2
),
345 ipcp_cval_get_cvalue_type (cval1
),
346 ipcp_cval_get_cvalue_type (cval2
)))
352 /* Create cval structure for method MT. */
354 ipcp_formal_create (struct cgraph_node
*mt
)
356 IPA_NODE_REF (mt
)->ipcp_lattices
=
357 XCNEWVEC (struct ipcp_lattice
, ipa_get_param_count (IPA_NODE_REF (mt
)));
360 /* Set cval structure of I-th formal of MT to CVAL. */
362 ipcp_method_cval_set (struct cgraph_node
*mt
, int i
, struct ipcp_lattice
*cval
)
364 IPA_NODE_REF (mt
)->ipcp_lattices
[i
].type
= cval
->type
;
365 ipcp_cval_set_cvalue (ipcp_method_cval (mt
, i
),
366 ipcp_cval_get_cvalue (cval
), cval
->type
);
369 /* Set type of cval structure of formal I of MT to CVAL_TYPE1. */
371 ipcp_method_cval_set_cvalue_type (struct cgraph_node
*mt
, int i
,
372 enum ipa_lattice_type type
)
374 IPA_NODE_REF (mt
)->ipcp_lattices
[i
].type
= type
;
377 /* Set type of cval structure of formal I of MT to CVAL_TYPE1. */
379 ipcp_method_cval_set_lattice_type (struct cgraph_node
*mt
, int i
,
380 enum ipa_lattice_type type
)
382 IPA_NODE_REF (mt
)->ipcp_lattices
[i
].type
= type
;
385 /* Print ipcp_cval data structures to F. */
387 ipcp_method_cval_print (FILE * f
)
389 struct cgraph_node
*node
;
393 fprintf (f
, "\nCVAL PRINT\n");
394 for (node
= cgraph_nodes
; node
; node
= node
->next
)
396 fprintf (f
, "Printing cvals %s:\n", cgraph_node_name (node
));
397 count
= ipa_get_param_count (IPA_NODE_REF (node
));
398 for (i
= 0; i
< count
; i
++)
400 if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
))
402 || ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
)) ==
405 fprintf (f
, " param [%d]: ", i
);
406 fprintf (f
, "type is CONST ");
408 ipcp_cval_get_cvalue (ipcp_method_cval (node
, i
));
409 print_generic_expr (f
, cvalue
, 0);
412 else if (ipcp_method_cval (node
, i
)->type
== IPA_TOP
)
413 fprintf (f
, "param [%d]: type is TOP \n", i
);
415 fprintf (f
, "param [%d]: type is BOTTOM \n", i
);
420 /* Initialize ipcp_cval array of MT with IPA_TOP values.
421 All cvals for a method's formal parameters are initialized to IPA_BOTTOM
422 The currently supported types are integer types, real types and
423 Fortran constants (i.e. references to constants defined as
424 const_decls). All other types are not analyzed and therefore are
425 assigned with IPA_BOTTOM. */
427 ipcp_method_cval_init (struct cgraph_node
*mt
)
432 ipcp_formal_create (mt
);
433 for (i
= 0; i
< ipa_get_param_count (IPA_NODE_REF (mt
)) ; i
++)
435 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (mt
), i
);
436 if (INTEGRAL_TYPE_P (TREE_TYPE (parm_tree
))
437 || SCALAR_FLOAT_TYPE_P (TREE_TYPE (parm_tree
))
438 || POINTER_TYPE_P (TREE_TYPE (parm_tree
)))
439 ipcp_method_cval_set_cvalue_type (mt
, i
, IPA_TOP
);
441 ipcp_method_cval_set_cvalue_type (mt
, i
, IPA_BOTTOM
);
445 /* Create a new assignment statment and make
446 it the first statement in the function FN
448 PARM1 is the lhs of the assignment and
451 constant_val_insert (tree parm1
, tree val
)
453 tree init_stmt
= NULL
;
456 init_stmt
= build_gimple_modify_stmt (parm1
, val
);
460 e_step
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FUNCTION (cfun
));
461 bsi_insert_on_edge_immediate (e_step
, init_stmt
);
465 /* build INTEGER_CST tree with type TREE_TYPE and
466 value according to CVALUE. Return the tree. */
468 build_const_val (tree cvalue
, enum ipa_lattice_type type
, tree tree_type
)
470 tree const_val
= NULL
;
472 gcc_assert (ipcp_type_is_const (type
));
473 const_val
= fold_convert (tree_type
, cvalue
);
477 /* Build the tree representing the constant and call
478 constant_val_insert(). */
480 ipcp_propagate_const (struct cgraph_node
*mt
, int param
,
481 tree cvalue
, enum ipa_lattice_type type
)
487 fprintf (dump_file
, "propagating const to %s\n", cgraph_node_name (mt
));
488 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (mt
), param
);
489 const_val
= build_const_val (cvalue
, type
, TREE_TYPE (parm_tree
));
490 constant_val_insert (parm_tree
, const_val
);
493 /* Compute the proper scale for NODE. It is the ratio between
494 the number of direct calls (represented on the incoming
495 cgraph_edges) and sum of all invocations of NODE (represented
496 as count in cgraph_node). */
498 ipcp_method_compute_scale (struct cgraph_node
*node
)
501 struct cgraph_edge
*cs
;
504 /* Compute sum of all counts of callers. */
505 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
507 if (node
->count
== 0)
508 ipcp_method_set_scale (node
, 0);
510 ipcp_method_set_scale (node
, sum
* REG_BR_PROB_BASE
/ node
->count
);
513 /* Initialization and computation of IPCP data structures.
514 It is an intraprocedural
515 analysis of methods, which gathers information to be propagated
518 ipcp_init_stage (void)
520 struct cgraph_node
*node
;
521 struct cgraph_edge
*cs
;
523 for (node
= cgraph_nodes
; node
; node
= node
->next
)
525 ipa_count_formal_params (node
);
526 ipa_create_param_decls_array (node
);
527 ipcp_method_cval_init (node
);
528 ipa_detect_param_modifications (node
);
529 ipcp_method_compute_scale (node
);
531 for (node
= cgraph_nodes
; node
; node
= node
->next
)
533 /* building jump functions */
534 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
536 ipa_count_arguments (cs
);
537 if (ipa_get_cs_argument_count (IPA_EDGE_REF (cs
))
538 != ipa_get_param_count (IPA_NODE_REF (cs
->callee
)))
540 /* Handle cases of functions with
541 a variable number of parameters. */
542 ipa_set_called_with_variable_arg (IPA_NODE_REF (cs
->callee
));
545 ipa_compute_jump_functions (cs
);
550 /* Return true if there are some formal parameters whose value is IPA_TOP.
551 Change their values to IPA_BOTTOM, since they weren't determined. */
553 ipcp_after_propagate (void)
556 struct cgraph_node
*node
;
560 for (node
= cgraph_nodes
; node
; node
= node
->next
)
562 count
= ipa_get_param_count (IPA_NODE_REF (node
));
563 for (i
= 0; i
< count
; i
++)
564 if (ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
)) == IPA_TOP
)
567 ipcp_method_cval_set_cvalue_type (node
, i
, IPA_BOTTOM
);
573 /* Interprocedural analysis. The algorithm propagates constants from
574 the caller's parameters to the callee's arguments. */
576 ipcp_propagate_stage (void)
579 struct ipcp_lattice cval1
= { IPA_BOTTOM
, NULL
}, cval
= { IPA_BOTTOM
, NULL
};
580 struct ipcp_lattice
*cval2
;
581 struct cgraph_node
*mt
, *callee
;
582 struct cgraph_edge
*cs
;
583 struct ipa_jump_func
*jump_func
;
584 enum jump_func_type type
;
585 union jump_func_value
*jf_value
;
586 struct ipa_func_list
*wl
;
589 /* Initialize worklist to contain all functions. */
590 wl
= ipa_init_func_list ();
593 mt
= ipa_pop_func_from_list (&wl
);
594 for (cs
= mt
->callees
; cs
; cs
= cs
->next_callee
)
597 if (ipa_is_called_with_var_arguments (IPA_NODE_REF (callee
)))
599 count
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
600 for (i
= 0; i
< count
; i
++)
602 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
603 type
= jump_func
->type
;
604 jf_value
= &jump_func
->value
;
605 ipcp_cval_compute (&cval1
, mt
, type
, jf_value
);
606 cval2
= ipcp_method_cval (callee
, i
);
607 ipcp_cval_meet (&cval
, &cval1
, cval2
);
608 if (ipcp_cval_changed (&cval
, cval2
))
610 ipcp_method_cval_set (callee
, i
, &cval
);
611 ipa_push_func_to_list (&wl
, callee
);
618 /* Call the constant propagation algorithm and re-call it if necessary
619 (if there are undetermined values left). */
621 ipcp_iterate_stage (void)
623 ipcp_propagate_stage ();
624 if (ipcp_after_propagate ())
625 /* Some cvals have changed from IPA_TOP to IPA_BOTTOM.
626 This change should be propagated. */
627 ipcp_propagate_stage ();
630 /* Check conditions to forbid constant insertion to MT. */
632 ipcp_method_dont_insert_const (struct cgraph_node
*mt
)
634 /* ??? Handle pending sizes case. */
635 if (DECL_UNINLINABLE (mt
->decl
))
640 /* Print ipa_jump_func data structures to F. */
642 ipcp_callsite_param_print (FILE * f
)
644 struct cgraph_node
*node
;
646 struct cgraph_edge
*cs
;
647 struct ipa_jump_func
*jump_func
;
648 enum jump_func_type type
;
651 fprintf (f
, "\nCALLSITE PARAM PRINT\n");
652 for (node
= cgraph_nodes
; node
; node
= node
->next
)
654 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
656 fprintf (f
, "callsite %s ", cgraph_node_name (node
));
657 fprintf (f
, "-> %s :: \n", cgraph_node_name (cs
->callee
));
659 if (ipa_is_called_with_var_arguments (IPA_NODE_REF (cs
->callee
)))
662 count
= ipa_get_cs_argument_count (IPA_EDGE_REF (cs
));
663 for (i
= 0; i
< count
; i
++)
665 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
666 type
= jump_func
->type
;
668 fprintf (f
, " param %d: ", i
);
669 if (type
== IPA_UNKNOWN
)
670 fprintf (f
, "UNKNOWN\n");
671 else if (type
== IPA_CONST
|| type
== IPA_CONST_REF
)
673 info_type
= jump_func
->value
.constant
;
674 fprintf (f
, "CONST : ");
675 print_generic_expr (f
, info_type
, 0);
678 else if (type
== IPA_PASS_THROUGH
)
680 fprintf (f
, "PASS THROUGH : ");
681 fprintf (f
, "%d\n", jump_func
->value
.formal_id
);
688 /* Print count scale data structures. */
690 ipcp_method_scale_print (FILE * f
)
692 struct cgraph_node
*node
;
694 for (node
= cgraph_nodes
; node
; node
= node
->next
)
696 fprintf (f
, "printing scale for %s: ", cgraph_node_name (node
));
697 fprintf (f
, "value is " HOST_WIDE_INT_PRINT_DEC
698 " \n", (HOST_WIDE_INT
) ipcp_method_get_scale (node
));
702 /* Print counts of all cgraph nodes. */
704 ipcp_profile_mt_count_print (FILE * f
)
706 struct cgraph_node
*node
;
708 for (node
= cgraph_nodes
; node
; node
= node
->next
)
710 fprintf (f
, "method %s: ", cgraph_node_name (node
));
711 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
712 " \n", (HOST_WIDE_INT
) node
->count
);
716 /* Print counts of all cgraph edges. */
718 ipcp_profile_cs_count_print (FILE * f
)
720 struct cgraph_node
*node
;
721 struct cgraph_edge
*cs
;
723 for (node
= cgraph_nodes
; node
; node
= node
->next
)
725 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
727 fprintf (f
, "%s -> %s ", cgraph_node_name (cs
->caller
),
728 cgraph_node_name (cs
->callee
));
729 fprintf (f
, "count is " HOST_WIDE_INT_PRINT_DEC
" \n",
730 (HOST_WIDE_INT
) cs
->count
);
735 /* Print all counts and probabilities of cfg edges of all methods. */
737 ipcp_profile_edge_print (FILE * f
)
739 struct cgraph_node
*node
;
744 for (node
= cgraph_nodes
; node
; node
= node
->next
)
746 fprintf (f
, "method %s: \n", cgraph_node_name (node
));
747 if (DECL_SAVED_TREE (node
->decl
))
750 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
751 fprintf (f
, "ENTRY: ");
752 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
753 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
756 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
759 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
761 fprintf (f
, "edge ENTRY -> EXIT, Count");
763 fprintf (f
, "edge ENTRY -> %d, Count", e
->dest
->index
);
764 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
765 " Prob %d\n", (HOST_WIDE_INT
) e
->count
,
768 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
770 fprintf (f
, "bb[%d]: ", bb
->index
);
771 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
772 " %d\n", (HOST_WIDE_INT
) bb
->count
, bb
->frequency
);
773 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
776 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION
778 fprintf (f
, "edge %d -> EXIT, Count", e
->src
->index
);
780 fprintf (f
, "edge %d -> %d, Count", e
->src
->index
,
782 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
" Prob %d\n",
783 (HOST_WIDE_INT
) e
->count
, e
->probability
);
790 /* Print counts and frequencies for all basic blocks of all methods. */
792 ipcp_profile_bb_print (FILE * f
)
795 struct cgraph_node
*node
;
797 for (node
= cgraph_nodes
; node
; node
= node
->next
)
799 fprintf (f
, "method %s: \n", cgraph_node_name (node
));
803 ENTRY_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
804 fprintf (f
, "ENTRY: Count");
805 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
806 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
809 FOR_EACH_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
811 fprintf (f
, "bb[%d]: Count", bb
->index
);
812 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
813 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
817 EXIT_BLOCK_PTR_FOR_FUNCTION (DECL_STRUCT_FUNCTION (node
->decl
));
818 fprintf (f
, "EXIT: Count");
819 fprintf (f
, " " HOST_WIDE_INT_PRINT_DEC
820 " Frequency %d\n", (HOST_WIDE_INT
) bb
->count
,
827 /* Print all IPCP data structures to F. */
829 ipcp_structures_print (FILE * f
)
831 ipcp_method_cval_print (f
);
832 ipcp_method_scale_print (f
);
833 ipa_print_all_tree_maps (f
);
834 ipa_print_all_params_modified (f
);
835 ipcp_callsite_param_print (f
);
838 /* Print profile info for all methods. */
840 ipcp_profile_print (FILE * f
)
842 fprintf (f
, "\nNODE COUNTS :\n");
843 ipcp_profile_mt_count_print (f
);
844 fprintf (f
, "\nCS COUNTS stage:\n");
845 ipcp_profile_cs_count_print (f
);
846 fprintf (f
, "\nBB COUNTS and FREQUENCIES :\n");
847 ipcp_profile_bb_print (f
);
848 fprintf (f
, "\nCFG EDGES COUNTS and PROBABILITIES :\n");
849 ipcp_profile_edge_print (f
);
852 /* Build and initialize ipa_replace_map struct
853 according to TYPE. This struct is read by versioning, which
854 operates according to the flags sent. PARM_TREE is the
855 formal's tree found to be constant. CVALUE represents the constant. */
856 static struct ipa_replace_map
*
857 ipcp_replace_map_create (struct function
*func
, enum ipa_lattice_type type
,
858 tree parm_tree
, tree cvalue
)
860 struct ipa_replace_map
*replace_map
;
863 replace_map
= XCNEW (struct ipa_replace_map
);
864 gcc_assert (ipcp_type_is_const (type
));
865 if (type
!= IPA_CONST_VALUE_REF
866 && is_gimple_reg (parm_tree
) && gimple_default_def (func
, parm_tree
)
867 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_default_def (func
, parm_tree
)))
870 fprintf (dump_file
, "replacing param with const\n");
871 const_val
= build_const_val (cvalue
, type
, TREE_TYPE (parm_tree
));
872 replace_map
->old_tree
=gimple_default_def (func
, parm_tree
);
873 replace_map
->new_tree
= const_val
;
874 replace_map
->replace_p
= true;
875 replace_map
->ref_p
= false;
879 replace_map
->old_tree
= NULL
;
880 replace_map
->new_tree
= NULL
;
881 replace_map
->replace_p
= false;
882 replace_map
->ref_p
= false;
888 /* Return true if this callsite should be redirected to
889 the orig callee (instead of the cloned one). */
891 ipcp_redirect (struct cgraph_edge
*cs
)
893 struct cgraph_node
*caller
, *callee
, *orig_callee
;
895 struct ipa_jump_func
*jump_func
;
896 enum jump_func_type type
;
897 enum ipa_lattice_type lattice_type
;
901 orig_callee
= ipcp_method_orig_node (callee
);
902 count
= ipa_get_param_count (IPA_NODE_REF (orig_callee
));
903 for (i
= 0; i
< count
; i
++)
906 ipcp_cval_get_cvalue_type (ipcp_method_cval (orig_callee
, i
));
907 if (ipcp_type_is_const (lattice_type
))
909 jump_func
= ipa_get_ith_jump_func (IPA_EDGE_REF (cs
), i
);
910 type
= jump_func
->type
;
911 if (type
!= IPA_CONST
&& type
!= IPA_CONST_REF
)
919 /* Fix the callsites and the callgraph after function cloning was done. */
921 ipcp_update_callgraph (void)
923 struct cgraph_node
*node
, *orig_callee
;
924 struct cgraph_edge
*cs
;
926 for (node
= cgraph_nodes
; node
; node
= node
->next
)
928 /* want to fix only original nodes */
929 if (ipcp_method_is_cloned (node
))
931 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
932 if (ipcp_method_is_cloned (cs
->callee
))
934 /* Callee is a cloned node */
935 orig_callee
= ipcp_method_orig_node (cs
->callee
);
936 if (ipcp_redirect (cs
))
938 cgraph_redirect_edge_callee (cs
, orig_callee
);
939 TREE_OPERAND (CALL_EXPR_FN (get_call_expr_in (cs
->call_stmt
)),
947 /* Update all cfg basic blocks in NODE according to SCALE. */
949 ipcp_update_bb_counts (struct cgraph_node
*node
, gcov_type scale
)
953 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
954 bb
->count
= bb
->count
* scale
/ REG_BR_PROB_BASE
;
957 /* Update all cfg edges in NODE according to SCALE. */
959 ipcp_update_edges_counts (struct cgraph_node
*node
, gcov_type scale
)
965 FOR_ALL_BB_FN (bb
, DECL_STRUCT_FUNCTION (node
->decl
))
966 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
967 e
->count
= e
->count
* scale
/ REG_BR_PROB_BASE
;
970 /* Update profiling info for versioned methods and the
971 methods they were versioned from. */
973 ipcp_update_profiling (void)
975 struct cgraph_node
*node
, *orig_node
;
976 gcov_type scale
, scale_complement
;
977 struct cgraph_edge
*cs
;
979 for (node
= cgraph_nodes
; node
; node
= node
->next
)
981 if (ipcp_method_is_cloned (node
))
983 orig_node
= ipcp_method_orig_node (node
);
984 scale
= ipcp_method_get_scale (orig_node
);
985 node
->count
= orig_node
->count
* scale
/ REG_BR_PROB_BASE
;
986 scale_complement
= REG_BR_PROB_BASE
- scale
;
988 orig_node
->count
* scale_complement
/ REG_BR_PROB_BASE
;
989 for (cs
= node
->callees
; cs
; cs
= cs
->next_callee
)
990 cs
->count
= cs
->count
* scale
/ REG_BR_PROB_BASE
;
991 for (cs
= orig_node
->callees
; cs
; cs
= cs
->next_callee
)
992 cs
->count
= cs
->count
* scale_complement
/ REG_BR_PROB_BASE
;
993 ipcp_update_bb_counts (node
, scale
);
994 ipcp_update_bb_counts (orig_node
, scale_complement
);
995 ipcp_update_edges_counts (node
, scale
);
996 ipcp_update_edges_counts (orig_node
, scale_complement
);
1001 /* Propagate the constant parameters found by ipcp_iterate_stage()
1002 to the function's code. */
1004 ipcp_insert_stage (void)
1006 struct cgraph_node
*node
, *node1
= NULL
;
1009 VEC (cgraph_edge_p
, heap
) * redirect_callers
;
1010 varray_type replace_trees
;
1011 struct cgraph_edge
*cs
;
1012 int node_callers
, count
;
1014 enum ipa_lattice_type type
;
1015 struct ipa_replace_map
*replace_param
;
1017 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1019 /* Propagation of the constant is forbidden in
1020 certain conditions. */
1021 if (!node
->analyzed
|| ipcp_method_dont_insert_const (node
)
1022 || ipa_is_called_with_var_arguments (IPA_NODE_REF (node
)))
1025 count
= ipa_get_param_count (IPA_NODE_REF (node
));
1026 for (i
= 0; i
< count
; i
++)
1028 type
= ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
));
1029 if (ipcp_type_is_const (type
))
1032 if (const_param
== 0)
1034 VARRAY_GENERIC_PTR_INIT (replace_trees
, const_param
, "replace_trees");
1035 for (i
= 0; i
< count
; i
++)
1037 type
= ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
));
1038 if (ipcp_type_is_const (type
))
1040 cvalue
= ipcp_cval_get_cvalue (ipcp_method_cval (node
, i
));
1041 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), i
);
1043 ipcp_replace_map_create (DECL_STRUCT_FUNCTION (node
->decl
),
1044 type
, parm_tree
, cvalue
);
1045 VARRAY_PUSH_GENERIC_PTR (replace_trees
, replace_param
);
1048 /* Compute how many callers node has. */
1050 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1052 redirect_callers
= VEC_alloc (cgraph_edge_p
, heap
, node_callers
);
1053 for (cs
= node
->callers
; cs
!= NULL
; cs
= cs
->next_caller
)
1054 VEC_quick_push (cgraph_edge_p
, redirect_callers
, cs
);
1055 /* Redirecting all the callers of the node to the
1056 new versioned node. */
1058 cgraph_function_versioning (node
, redirect_callers
, replace_trees
);
1059 VEC_free (cgraph_edge_p
, heap
, redirect_callers
);
1060 VARRAY_CLEAR (replace_trees
);
1064 fprintf (dump_file
, "versioned function %s\n",
1065 cgraph_node_name (node
));
1066 ipcp_cloned_create (node
, node1
);
1067 if (const_param
> 0)
1069 push_cfun (DECL_STRUCT_FUNCTION (node1
->decl
));
1070 tree_register_cfg_hooks ();
1071 current_function_decl
= node1
->decl
;
1073 for (i
= 0; i
< count
; i
++)
1075 type
= ipcp_cval_get_cvalue_type (ipcp_method_cval (node
, i
));
1076 if (ipcp_type_is_const (type
))
1078 cvalue
= ipcp_cval_get_cvalue (ipcp_method_cval (node
, i
));
1079 parm_tree
= ipa_get_ith_param (IPA_NODE_REF (node
), i
);
1080 if (type
!= IPA_CONST_VALUE_REF
&& !is_gimple_reg (parm_tree
))
1081 ipcp_propagate_const (node1
, i
, cvalue
, type
);
1084 if (gimple_in_ssa_p (cfun
))
1086 update_ssa (TODO_update_ssa
);
1087 #ifdef ENABLE_CHECKING
1091 free_dominance_info (CDI_DOMINATORS
);
1092 free_dominance_info (CDI_POST_DOMINATORS
);
1094 current_function_decl
= NULL
;
1097 dump_function_to_file (node1
->decl
, dump_file
, dump_flags
);
1099 ipcp_update_callgraph ();
1100 ipcp_update_profiling ();
1103 /* The IPCP driver. */
1108 fprintf (dump_file
, "\nIPA constant propagation start:\n");
1109 ipa_create_all_node_params ();
1110 ipa_create_all_edge_args ();
1111 /* 1. Call the init stage to initialize
1112 the ipa_node_params and ipa_edge_args structures. */
1116 fprintf (dump_file
, "\nIPA structures before propagation:\n");
1117 ipcp_structures_print (dump_file
);
1119 /* 2. Do the interprocedural propagation. */
1120 ipcp_iterate_stage ();
1123 fprintf (dump_file
, "\nIPA structures after propagation:\n");
1124 ipcp_structures_print (dump_file
);
1125 fprintf (dump_file
, "\nProfiling info before insert stage:\n");
1126 ipcp_profile_print (dump_file
);
1128 /* 3. Insert the constants found to the functions. */
1129 ipcp_insert_stage ();
1132 fprintf (dump_file
, "\nProfiling info after insert stage:\n");
1133 ipcp_profile_print (dump_file
);
1135 /* Free all IPCP structures. */
1136 ipa_free_all_node_params ();
1137 ipa_free_all_edge_args ();
1139 fprintf (dump_file
, "\nIPA constant propagation end\n");
1140 cgraph_remove_unreachable_nodes (true, NULL
);
1144 /* Gate for IPCP optimization. */
1146 cgraph_gate_cp (void)
1151 struct simple_ipa_opt_pass pass_ipa_cp
=
1156 cgraph_gate_cp
, /* gate */
1157 ipcp_driver
, /* execute */
1160 0, /* static_pass_number */
1161 TV_IPA_CONSTANT_PROP
, /* tv_id */
1162 0, /* properties_required */
1163 PROP_trees
, /* properties_provided */
1164 0, /* properties_destroyed */
1165 0, /* todo_flags_start */
1166 TODO_dump_cgraph
| TODO_dump_func
/* todo_flags_finish */