1 /* Callgraph based analysis of static variables.
2 Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Kenneth Zadeck <zadeck@naturalbridge.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 /* This file marks functions as being either const (TREE_READONLY) or
22 pure (DECL_PURE_P). It can also set a variant of these that
23 are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P).
25 This must be run after inlining decisions have been made since
26 otherwise, the local sets will not contain information that is
27 consistent with post inlined state. The global sets are not prone
28 to this problem since they are by definition transitive. */
30 /* The code in this module is called by the ipa pass manager. It
31 should be one of the later passes since it's information is used by
32 the rest of the compilation. */
36 #include "coretypes.h"
39 #include "tree-flow.h"
40 #include "tree-inline.h"
41 #include "tree-pass.h"
42 #include "langhooks.h"
43 #include "pointer-set.h"
45 #include "ipa-utils.h"
52 #include "diagnostic.h"
53 #include "langhooks.h"
56 static struct pointer_set_t
*visited_nodes
;
58 /* Lattice values for const and pure functions. Everything starts out
59 being const, then may drop to pure and then neither depending on
61 enum pure_const_state_e
68 /* Holder inserted into the ipa_dfs_info aux field to hold the
72 enum pure_const_state_e pure_const_state
;
74 bool state_set_in_source
;
77 typedef struct funct_state_d
* funct_state
;
79 /* Return the function state from NODE. */
81 static inline funct_state
82 get_function_state (struct cgraph_node
*node
)
84 struct ipa_dfs_info
* info
= (struct ipa_dfs_info
*) node
->aux
;
85 return (funct_state
) info
->aux
;
88 /* Check to see if the use (or definition when CHECKING_WRITE is true)
89 variable T is legal in a function that is either pure or const. */
92 check_decl (funct_state local
,
93 tree t
, bool checking_write
)
95 /* If the variable has the "used" attribute, treat it as if it had a
96 been touched by the devil. */
97 if (lookup_attribute ("used", DECL_ATTRIBUTES (t
)))
99 local
->pure_const_state
= IPA_NEITHER
;
100 local
->looping
= false;
104 /* Do not want to do anything with volatile except mark any
105 function that uses one to be not const or pure. */
106 if (TREE_THIS_VOLATILE (t
))
108 local
->pure_const_state
= IPA_NEITHER
;
109 local
->looping
= false;
113 /* Do not care about a local automatic that is not static. */
114 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
117 /* Since we have dealt with the locals and params cases above, if we
118 are CHECKING_WRITE, this cannot be a pure or constant
122 local
->pure_const_state
= IPA_NEITHER
;
123 local
->looping
= false;
127 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
129 /* If the front end set the variable to be READONLY and
130 constant, we can allow this variable in pure or const
131 functions but the scope is too large for our analysis to set
132 these bits ourselves. */
134 if (TREE_READONLY (t
)
136 && is_gimple_min_invariant (DECL_INITIAL (t
)))
137 ; /* Read of a constant, do not change the function state. */
140 /* Just a regular read. */
141 if (local
->pure_const_state
== IPA_CONST
)
142 local
->pure_const_state
= IPA_PURE
;
146 /* Compilation level statics can be read if they are readonly
148 if (TREE_READONLY (t
))
151 /* Just a regular read. */
152 if (local
->pure_const_state
== IPA_CONST
)
153 local
->pure_const_state
= IPA_PURE
;
156 /* If T is a VAR_DECL check to see if it is an allowed reference. */
159 check_operand (funct_state local
,
160 tree t
, bool checking_write
)
164 if (TREE_CODE (t
) == VAR_DECL
)
165 check_decl (local
, t
, checking_write
);
168 /* Examine tree T for references. */
171 check_tree (funct_state local
, tree t
, bool checking_write
)
173 if ((TREE_CODE (t
) == EXC_PTR_EXPR
) || (TREE_CODE (t
) == FILTER_EXPR
)
174 || TREE_CODE (t
) == SSA_NAME
)
177 /* Any tree which is volatile disqualifies this function from being
179 if (TREE_THIS_VOLATILE (t
))
181 local
->pure_const_state
= IPA_NEITHER
;
182 local
->looping
= false;
186 while (TREE_CODE (t
) == REALPART_EXPR
187 || TREE_CODE (t
) == IMAGPART_EXPR
188 || handled_component_p (t
))
190 if (TREE_CODE (t
) == ARRAY_REF
)
191 check_operand (local
, TREE_OPERAND (t
, 1), false);
192 t
= TREE_OPERAND (t
, 0);
195 /* The bottom of an indirect reference can only be read, not
197 if (INDIRECT_REF_P (t
))
199 check_tree (local
, TREE_OPERAND (t
, 0), false);
201 /* Any indirect reference that occurs on the lhs
202 disqualifies the function from being pure or const. Any
203 indirect reference that occurs on the rhs disqualifies the
204 function from being const. */
207 local
->pure_const_state
= IPA_NEITHER
;
208 local
->looping
= false;
211 else if (local
->pure_const_state
== IPA_CONST
)
212 local
->pure_const_state
= IPA_PURE
;
216 check_operand (local
, t
, checking_write
);
219 /* Scan tree T to see if there are any addresses taken in within T. */
222 look_for_address_of (funct_state local
, tree t
)
224 if (TREE_CODE (t
) == ADDR_EXPR
)
226 tree x
= get_base_var (t
);
227 if (TREE_CODE (x
) == VAR_DECL
)
229 check_decl (local
, x
, false);
231 /* Taking the address of something appears to be reasonable
232 in PURE code. Not allowed in const. */
233 if (local
->pure_const_state
== IPA_CONST
)
234 local
->pure_const_state
= IPA_PURE
;
239 /* Check to see if T is a read or address of operation on a var we are
240 interested in analyzing. LOCAL is passed in to get access to its
244 check_rhs_var (funct_state local
, tree t
)
246 look_for_address_of (local
, t
);
248 /* Memcmp and strlen can both trap and they are declared pure. */
249 if (tree_could_trap_p (t
)
250 && local
->pure_const_state
== IPA_CONST
)
251 local
->pure_const_state
= IPA_PURE
;
253 check_tree(local
, t
, false);
256 /* Check to see if T is an assignment to a var we are interested in
257 analyzing. LOCAL is passed in to get access to its bit vectors. */
260 check_lhs_var (funct_state local
, tree t
)
262 /* Memcmp and strlen can both trap and they are declared pure.
263 Which seems to imply that we can apply the same rule here. */
264 if (tree_could_trap_p (t
)
265 && local
->pure_const_state
== IPA_CONST
)
266 local
->pure_const_state
= IPA_PURE
;
268 check_tree(local
, t
, true);
271 /* This is a scaled down version of get_asm_expr_operands from
272 tree_ssa_operands.c. The version there runs much later and assumes
273 that aliasing information is already available. Here we are just
274 trying to find if the set of inputs and outputs contain references
275 or address of operations to local static variables. STMT is the
276 actual asm statement. */
279 get_asm_expr_operands (funct_state local
, gimple stmt
)
281 size_t noutputs
= gimple_asm_noutputs (stmt
);
282 const char **oconstraints
283 = (const char **) alloca ((noutputs
) * sizeof (const char *));
286 const char *constraint
;
287 bool allows_mem
, allows_reg
, is_inout
;
289 for (i
= 0; i
< noutputs
; i
++)
291 op
= gimple_asm_output_op (stmt
, i
);
292 oconstraints
[i
] = constraint
293 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op
)));
294 parse_output_constraint (&constraint
, i
, 0, 0,
295 &allows_mem
, &allows_reg
, &is_inout
);
297 check_lhs_var (local
, TREE_VALUE (op
));
300 for (i
= 0; i
< gimple_asm_ninputs (stmt
); i
++)
302 op
= gimple_asm_input_op (stmt
, i
);
304 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (op
)));
305 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0,
306 oconstraints
, &allows_mem
, &allows_reg
);
308 check_rhs_var (local
, TREE_VALUE (op
));
311 for (i
= 0; i
< gimple_asm_nclobbers (stmt
); i
++)
313 op
= gimple_asm_clobber_op (stmt
, i
);
314 if (simple_cst_equal(TREE_VALUE (op
), memory_identifier_string
) == 1)
315 /* Abandon all hope, ye who enter here. */
316 local
->pure_const_state
= IPA_NEITHER
;
319 if (gimple_asm_volatile_p (stmt
))
320 local
->pure_const_state
= IPA_NEITHER
;
323 /* Check the parameters of a function call to CALL_EXPR to see if
324 there are any references in the parameters that are not allowed for
325 pure or const functions. Also check to see if this is either an
326 indirect call, a call outside the compilation unit, or has special
327 attributes that may also effect the purity. The CALL_EXPR node for
328 the entire call expression. */
331 check_call (funct_state local
, gimple call
)
333 int flags
= gimple_call_flags (call
);
334 tree lhs
, callee_t
= gimple_call_fndecl (call
);
335 struct cgraph_node
* callee
;
336 enum availability avail
= AVAIL_NOT_AVAILABLE
;
339 lhs
= gimple_call_lhs (call
);
341 check_lhs_var (local
, lhs
);
343 for (i
= 0; i
< gimple_call_num_args (call
); i
++)
344 check_rhs_var (local
, gimple_call_arg (call
, i
));
346 /* The const and pure flags are set by a variety of places in the
347 compiler (including here). If someone has already set the flags
348 for the callee, (such as for some of the builtins) we will use
349 them, otherwise we will compute our own information.
351 Const and pure functions have less clobber effects than other
352 functions so we process these first. Otherwise if it is a call
353 outside the compilation unit or an indirect call we punt. This
354 leaves local calls which will be processed by following the call
358 callee
= cgraph_node(callee_t
);
359 avail
= cgraph_function_body_availability (callee
);
361 /* When bad things happen to bad functions, they cannot be const
363 if (setjmp_call_p (callee_t
))
365 local
->pure_const_state
= IPA_NEITHER
;
366 local
->looping
= false;
369 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
370 switch (DECL_FUNCTION_CODE (callee_t
))
372 case BUILT_IN_LONGJMP
:
373 case BUILT_IN_NONLOCAL_GOTO
:
374 local
->pure_const_state
= IPA_NEITHER
;
375 local
->looping
= false;
382 /* The callee is either unknown (indirect call) or there is just no
383 scannable code for it (external call) . We look to see if there
384 are any bits available for the callee (such as by declaration or
385 because it is builtin) and process solely on the basis of those
387 if (avail
== AVAIL_NOT_AVAILABLE
|| avail
== AVAIL_OVERWRITABLE
)
389 if (flags
& ECF_PURE
)
391 if (local
->pure_const_state
== IPA_CONST
)
392 local
->pure_const_state
= IPA_PURE
;
395 local
->pure_const_state
= IPA_NEITHER
;
399 /* We have the code and we will scan it for the effects. */
400 if (flags
& ECF_PURE
)
402 if (local
->pure_const_state
== IPA_CONST
)
403 local
->pure_const_state
= IPA_PURE
;
408 /* TP is the part of the tree currently under the microscope.
409 WALK_SUBTREES is part of the walk_tree api but is unused here.
410 DATA is cgraph_node of the function being walked. */
412 /* FIXME: When this is converted to run over SSA form, this code
413 should be converted to use the operand scanner. */
416 scan_function_op (tree
*tp
, int *walk_subtrees
, void *data
)
418 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
419 struct cgraph_node
*fn
= (struct cgraph_node
*) wi
->info
;
421 funct_state local
= get_function_state (fn
);
423 switch (TREE_CODE (t
))
426 if (DECL_INITIAL (t
))
427 walk_tree (&DECL_INITIAL (t
), scan_function_op
, data
, visited_nodes
);
432 /* This case is here to find addresses on rhs of constructors in
433 decl_initial of static variables. */
434 check_rhs_var (local
, t
);
445 scan_function_stmt (gimple_stmt_iterator
*gsi_p
,
447 struct walk_stmt_info
*wi
)
449 struct cgraph_node
*fn
= (struct cgraph_node
*) wi
->info
;
450 gimple stmt
= gsi_stmt (*gsi_p
);
451 funct_state local
= get_function_state (fn
);
453 switch (gimple_code (stmt
))
457 /* First look on the lhs and see what variable is stored to */
458 tree lhs
= gimple_assign_lhs (stmt
);
459 tree rhs1
= gimple_assign_rhs1 (stmt
);
460 tree rhs2
= gimple_assign_rhs2 (stmt
);
461 enum tree_code code
= gimple_assign_rhs_code (stmt
);
463 check_lhs_var (local
, lhs
);
465 /* For the purposes of figuring out what the cast affects */
467 /* Next check the operands on the rhs to see if they are ok. */
468 switch (TREE_CODE_CLASS (code
))
472 check_rhs_var (local
, rhs1
);
473 check_rhs_var (local
, rhs2
);
478 check_rhs_var (local
, rhs1
);
483 check_rhs_var (local
, rhs1
);
485 case tcc_declaration
:
486 check_rhs_var (local
, rhs1
);
492 check_rhs_var (local
, rhs1
);
501 *handled_ops_p
= true;
506 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
507 /* Target of long jump. */
509 local
->pure_const_state
= IPA_NEITHER
;
510 local
->looping
= false;
515 check_call (local
, stmt
);
516 *handled_ops_p
= true;
520 get_asm_expr_operands (local
, stmt
);
521 *handled_ops_p
= true;
530 /* This is the main routine for finding the reference patterns for
531 global variables within a function FN. */
534 analyze_function (struct cgraph_node
*fn
)
536 funct_state l
= XCNEW (struct funct_state_d
);
537 tree decl
= fn
->decl
;
538 struct ipa_dfs_info
* w_info
= (struct ipa_dfs_info
*) fn
->aux
;
542 l
->pure_const_state
= IPA_CONST
;
543 l
->state_set_in_source
= false;
544 if (DECL_LOOPING_CONST_OR_PURE_P (decl
))
549 /* If this function does not return normally or does not bind local,
550 do not touch this unless it has been marked as const or pure by the
552 if (TREE_THIS_VOLATILE (decl
)
553 || !targetm
.binds_local_p (decl
))
555 l
->pure_const_state
= IPA_NEITHER
;
559 if (TREE_READONLY (decl
))
561 l
->pure_const_state
= IPA_CONST
;
562 l
->state_set_in_source
= true;
564 if (DECL_PURE_P (decl
))
566 l
->pure_const_state
= IPA_PURE
;
567 l
->state_set_in_source
= true;
572 fprintf (dump_file
, "\n local analysis of %s with initial value = %d\n ",
573 cgraph_node_name (fn
),
574 l
->pure_const_state
);
577 if (!l
->state_set_in_source
)
579 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (decl
);
580 basic_block this_block
;
582 FOR_EACH_BB_FN (this_block
, this_cfun
)
584 gimple_stmt_iterator gsi
;
585 struct walk_stmt_info wi
;
587 memset (&wi
, 0, sizeof(wi
));
588 for (gsi
= gsi_start_bb (this_block
);
593 wi
.pset
= visited_nodes
;
594 walk_gimple_stmt (&gsi
, scan_function_stmt
, scan_function_op
,
596 if (l
->pure_const_state
== IPA_NEITHER
)
601 if (l
->pure_const_state
!= IPA_NEITHER
)
603 tree old_decl
= current_function_decl
;
604 /* Const functions cannot have back edges (an
605 indication of possible infinite loop side
608 current_function_decl
= fn
->decl
;
610 /* The C++ front end, has a tendency to some times jerk away
611 a function after it has created it. This should have
613 gcc_assert (DECL_STRUCT_FUNCTION (fn
->decl
));
615 push_cfun (DECL_STRUCT_FUNCTION (fn
->decl
));
617 if (mark_dfs_back_edges ())
618 l
->pure_const_state
= IPA_NEITHER
;
620 current_function_decl
= old_decl
;
628 fprintf (dump_file
, "after local analysis of %s with initial value = %d\n ",
629 cgraph_node_name (fn
),
630 l
->pure_const_state
);
635 /* Produce the global information by preforming a transitive closure
636 on the local information that was produced by ipa_analyze_function
637 and ipa_analyze_variable. */
640 static_execute (void)
642 struct cgraph_node
*node
;
643 struct cgraph_node
*w
;
644 struct cgraph_node
**order
=
645 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
646 int order_pos
= ipa_utils_reduced_inorder (order
, true, false);
648 struct ipa_dfs_info
* w_info
;
650 if (!memory_identifier_string
)
651 memory_identifier_string
= build_string(7, "memory");
653 /* There are some shared nodes, in particular the initializers on
654 static declarations. We do not need to scan them more than once
655 since all we would be interested in are the addressof
657 visited_nodes
= pointer_set_create ();
659 /* Process all of the functions.
661 We do not want to process any of the clones so we check that this
662 is a master clone. However, we do NOT process any
663 AVAIL_OVERWRITABLE functions (these are never clones) we cannot
664 guarantee that what we learn about the one we see will be true
665 for the one that overrides it.
667 for (node
= cgraph_nodes
; node
; node
= node
->next
)
668 if (node
->analyzed
&& cgraph_is_master_clone (node
))
669 analyze_function (node
);
671 pointer_set_destroy (visited_nodes
);
672 visited_nodes
= NULL
;
675 dump_cgraph (dump_file
);
676 ipa_utils_print_order(dump_file
, "reduced", order
, order_pos
);
679 /* Propagate the local information thru the call graph to produce
680 the global information. All the nodes within a cycle will have
681 the same info so we collapse cycles first. Then we can do the
682 propagation in one pass from the leaves to the roots. */
683 for (i
= 0; i
< order_pos
; i
++ )
685 enum pure_const_state_e pure_const_state
= IPA_CONST
;
686 bool looping
= false;
690 /* Find the worst state for any node in the cycle. */
694 funct_state w_l
= get_function_state (w
);
695 if (pure_const_state
< w_l
->pure_const_state
)
696 pure_const_state
= w_l
->pure_const_state
;
701 if (pure_const_state
== IPA_NEITHER
)
704 if (!w_l
->state_set_in_source
)
706 struct cgraph_edge
*e
;
712 for (e
= w
->callees
; e
; e
= e
->next_callee
)
714 struct cgraph_node
*y
= e
->callee
;
715 /* Only look at the master nodes and skip external nodes. */
716 y
= cgraph_master_clone (y
);
722 funct_state y_l
= get_function_state (y
);
723 if (pure_const_state
< y_l
->pure_const_state
)
724 pure_const_state
= y_l
->pure_const_state
;
725 if (pure_const_state
== IPA_NEITHER
)
732 w_info
= (struct ipa_dfs_info
*) w
->aux
;
733 w
= w_info
->next_cycle
;
736 /* Copy back the region's pure_const_state which is shared by
737 all nodes in the region. */
741 funct_state w_l
= get_function_state (w
);
743 /* All nodes within a cycle share the same info. */
744 if (!w_l
->state_set_in_source
)
746 w_l
->pure_const_state
= pure_const_state
;
747 switch (pure_const_state
)
750 TREE_READONLY (w
->decl
) = 1;
751 DECL_LOOPING_CONST_OR_PURE_P (w
->decl
) = looping
;
753 fprintf (dump_file
, "Function found to be %sconst: %s\n",
754 looping
? "looping " : "",
755 lang_hooks
.decl_printable_name(w
->decl
, 2));
759 DECL_PURE_P (w
->decl
) = 1;
760 DECL_LOOPING_CONST_OR_PURE_P (w
->decl
) = looping
;
762 fprintf (dump_file
, "Function found to be %spure: %s\n",
763 looping
? "looping " : "",
764 lang_hooks
.decl_printable_name(w
->decl
, 2));
771 w_info
= (struct ipa_dfs_info
*) w
->aux
;
772 w
= w_info
->next_cycle
;
777 for (node
= cgraph_nodes
; node
; node
= node
->next
)
778 /* Get rid of the aux information. */
781 w_info
= (struct ipa_dfs_info
*) node
->aux
;
793 gate_pure_const (void)
795 return (flag_ipa_pure_const
796 /* Don't bother doing anything if the program has errors. */
797 && !(errorcount
|| sorrycount
));
800 struct simple_ipa_opt_pass pass_ipa_pure_const
=
804 "pure-const", /* name */
805 gate_pure_const
, /* gate */
806 static_execute
, /* execute */
809 0, /* static_pass_number */
810 TV_IPA_PURE_CONST
, /* tv_id */
811 0, /* properties_required */
812 0, /* properties_provided */
813 0, /* properties_destroyed */
814 0, /* todo_flags_start */
815 0 /* todo_flags_finish */