1 /* Callgraph based analysis of static variables.
2 Copyright (C) 2004, 2005, 2007 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 mark functions as being either const (TREE_READONLY) or
24 This must be run after inlining decisions have been made since
25 otherwise, the local sets will not contain information that is
26 consistent with post inlined state. The global sets are not prone
27 to this problem since they are by definition transitive. */
29 /* The code in this module is called by the ipa pass manager. It
30 should be one of the later passes since it's information is used by
31 the rest of the compilation. */
35 #include "coretypes.h"
38 #include "tree-flow.h"
39 #include "tree-inline.h"
40 #include "tree-pass.h"
41 #include "langhooks.h"
42 #include "pointer-set.h"
44 #include "ipa-utils.h"
46 #include "tree-gimple.h"
51 #include "diagnostic.h"
52 #include "langhooks.h"
55 static struct pointer_set_t
*visited_nodes
;
57 /* Lattice values for const and pure functions. Everything starts out
58 being const, then may drop to pure and then neither depending on
60 enum pure_const_state_e
67 /* Holder inserted into the ipa_dfs_info aux field to hold the
71 enum pure_const_state_e pure_const_state
;
72 bool state_set_in_source
;
75 typedef struct funct_state_d
* funct_state
;
77 /* Return the function state from NODE. */
79 static inline funct_state
80 get_function_state (struct cgraph_node
*node
)
82 struct ipa_dfs_info
* info
= (struct ipa_dfs_info
*) node
->aux
;
83 return (funct_state
) info
->aux
;
86 /* Check to see if the use (or definition when CHECHING_WRITE is true)
87 variable T is legal in a function that is either pure or const. */
90 check_decl (funct_state local
,
91 tree t
, bool checking_write
)
93 /* If the variable has the "used" attribute, treat it as if it had a
94 been touched by the devil. */
95 if (lookup_attribute ("used", DECL_ATTRIBUTES (t
)))
97 local
->pure_const_state
= IPA_NEITHER
;
101 /* Do not want to do anything with volatile except mark any
102 function that uses one to be not const or pure. */
103 if (TREE_THIS_VOLATILE (t
))
105 local
->pure_const_state
= IPA_NEITHER
;
109 /* Do not care about a local automatic that is not static. */
110 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
113 /* Since we have dealt with the locals and params cases above, if we
114 are CHECKING_WRITE, this cannot be a pure or constant
117 local
->pure_const_state
= IPA_NEITHER
;
119 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
121 /* If the front end set the variable to be READONLY and
122 constant, we can allow this variable in pure or const
123 functions but the scope is too large for our analysis to set
124 these bits ourselves. */
126 if (TREE_READONLY (t
)
128 && is_gimple_min_invariant (DECL_INITIAL (t
)))
129 ; /* Read of a constant, do not change the function state. */
132 /* Just a regular read. */
133 if (local
->pure_const_state
== IPA_CONST
)
134 local
->pure_const_state
= IPA_PURE
;
138 /* Compilation level statics can be read if they are readonly
140 if (TREE_READONLY (t
))
143 /* Just a regular read. */
144 if (local
->pure_const_state
== IPA_CONST
)
145 local
->pure_const_state
= IPA_PURE
;
148 /* If T is a VAR_DECL check to see if it is an allowed reference. */
151 check_operand (funct_state local
,
152 tree t
, bool checking_write
)
156 if (TREE_CODE (t
) == VAR_DECL
)
157 check_decl (local
, t
, checking_write
);
160 /* Examine tree T for references. */
163 check_tree (funct_state local
, tree t
, bool checking_write
)
165 if ((TREE_CODE (t
) == EXC_PTR_EXPR
) || (TREE_CODE (t
) == FILTER_EXPR
)
166 || TREE_CODE (t
) == SSA_NAME
)
169 /* Any tree which is volatile disqualifies thie function from being
171 if (TREE_THIS_VOLATILE (t
))
173 local
->pure_const_state
= IPA_NEITHER
;
177 while (TREE_CODE (t
) == REALPART_EXPR
178 || TREE_CODE (t
) == IMAGPART_EXPR
179 || handled_component_p (t
))
181 if (TREE_CODE (t
) == ARRAY_REF
)
182 check_operand (local
, TREE_OPERAND (t
, 1), false);
183 t
= TREE_OPERAND (t
, 0);
186 /* The bottom of an indirect reference can only be read, not
188 if (INDIRECT_REF_P (t
))
190 check_tree (local
, TREE_OPERAND (t
, 0), false);
192 /* Any indirect reference that occurs on the lhs
193 disqualifies the function from being pure or const. Any
194 indirect reference that occurs on the rhs disqualifies the
195 function from being const. */
198 local
->pure_const_state
= IPA_NEITHER
;
201 else if (local
->pure_const_state
== IPA_CONST
)
202 local
->pure_const_state
= IPA_PURE
;
206 check_operand (local
, t
, checking_write
);
209 /* Scan tree T to see if there are any addresses taken in within T. */
212 look_for_address_of (funct_state local
, tree t
)
214 if (TREE_CODE (t
) == ADDR_EXPR
)
216 tree x
= get_base_var (t
);
217 if (TREE_CODE (x
) == VAR_DECL
)
219 check_decl (local
, x
, false);
221 /* Taking the address of something appears to be reasonable
222 in PURE code. Not allowed in const. */
223 if (local
->pure_const_state
== IPA_CONST
)
224 local
->pure_const_state
= IPA_PURE
;
229 /* Check to see if T is a read or address of operation on a var we are
230 interested in analyzing. LOCAL is passed in to get access to its
234 check_rhs_var (funct_state local
, tree t
)
236 look_for_address_of (local
, t
);
238 /* Memcmp and strlen can both trap and they are declared pure. */
239 if (tree_could_trap_p (t
)
240 && local
->pure_const_state
== IPA_CONST
)
241 local
->pure_const_state
= IPA_PURE
;
243 check_tree(local
, t
, false);
246 /* Check to see if T is an assignment to a var we are interested in
247 analyzing. LOCAL is passed in to get access to its bit vectors. */
250 check_lhs_var (funct_state local
, tree t
)
252 /* Memcmp and strlen can both trap and they are declared pure.
253 Which seems to imply that we can apply the same rule here. */
254 if (tree_could_trap_p (t
)
255 && local
->pure_const_state
== IPA_CONST
)
256 local
->pure_const_state
= IPA_PURE
;
258 check_tree(local
, t
, true);
261 /* This is a scaled down version of get_asm_expr_operands from
262 tree_ssa_operands.c. The version there runs much later and assumes
263 that aliasing information is already available. Here we are just
264 trying to find if the set of inputs and outputs contain references
265 or address of operations to local static variables. STMT is the
266 actual asm statement. */
269 get_asm_expr_operands (funct_state local
, tree stmt
)
271 int noutputs
= list_length (ASM_OUTPUTS (stmt
));
272 const char **oconstraints
273 = (const char **) alloca ((noutputs
) * sizeof (const char *));
276 const char *constraint
;
277 bool allows_mem
, allows_reg
, is_inout
;
279 for (i
=0, link
= ASM_OUTPUTS (stmt
); link
; ++i
, link
= TREE_CHAIN (link
))
281 oconstraints
[i
] = constraint
282 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
283 parse_output_constraint (&constraint
, i
, 0, 0,
284 &allows_mem
, &allows_reg
, &is_inout
);
286 check_lhs_var (local
, TREE_VALUE (link
));
289 for (link
= ASM_INPUTS (stmt
); link
; link
= TREE_CHAIN (link
))
292 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
293 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0,
294 oconstraints
, &allows_mem
, &allows_reg
);
296 check_rhs_var (local
, TREE_VALUE (link
));
299 for (link
= ASM_CLOBBERS (stmt
); link
; link
= TREE_CHAIN (link
))
300 if (simple_cst_equal(TREE_VALUE (link
), memory_identifier_string
) == 1)
301 /* Abandon all hope, ye who enter here. */
302 local
->pure_const_state
= IPA_NEITHER
;
304 if (ASM_VOLATILE_P (stmt
))
305 local
->pure_const_state
= IPA_NEITHER
;
308 /* Check the parameters of a function call to CALL_EXPR to see if
309 there are any references in the parameters that are not allowed for
310 pure or const functions. Also check to see if this is either an
311 indirect call, a call outside the compilation unit, or has special
312 attributes that may also effect the purity. The CALL_EXPR node for
313 the entire call expression. */
316 check_call (funct_state local
, tree call_expr
)
318 int flags
= call_expr_flags (call_expr
);
320 call_expr_arg_iterator iter
;
321 tree callee_t
= get_callee_fndecl (call_expr
);
322 struct cgraph_node
* callee
;
323 enum availability avail
= AVAIL_NOT_AVAILABLE
;
325 FOR_EACH_CALL_EXPR_ARG (operand
, iter
, call_expr
)
326 check_rhs_var (local
, operand
);
328 /* The const and pure flags are set by a variety of places in the
329 compiler (including here). If someone has already set the flags
330 for the callee, (such as for some of the builtins) we will use
331 them, otherwise we will compute our own information.
333 Const and pure functions have less clobber effects than other
334 functions so we process these first. Otherwise if it is a call
335 outside the compilation unit or an indirect call we punt. This
336 leaves local calls which will be processed by following the call
340 callee
= cgraph_node(callee_t
);
341 avail
= cgraph_function_body_availability (callee
);
343 /* When bad things happen to bad functions, they cannot be const
345 if (setjmp_call_p (callee_t
))
346 local
->pure_const_state
= IPA_NEITHER
;
348 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
349 switch (DECL_FUNCTION_CODE (callee_t
))
351 case BUILT_IN_LONGJMP
:
352 case BUILT_IN_NONLOCAL_GOTO
:
353 local
->pure_const_state
= IPA_NEITHER
;
360 /* The callee is either unknown (indirect call) or there is just no
361 scannable code for it (external call) . We look to see if there
362 are any bits available for the callee (such as by declaration or
363 because it is builtin) and process solely on the basis of those
365 if (avail
== AVAIL_NOT_AVAILABLE
|| avail
== AVAIL_OVERWRITABLE
)
367 if (flags
& ECF_PURE
)
369 if (local
->pure_const_state
== IPA_CONST
)
370 local
->pure_const_state
= IPA_PURE
;
373 local
->pure_const_state
= IPA_NEITHER
;
377 /* We have the code and we will scan it for the effects. */
378 if (flags
& ECF_PURE
)
380 if (local
->pure_const_state
== IPA_CONST
)
381 local
->pure_const_state
= IPA_PURE
;
386 /* TP is the part of the tree currently under the microscope.
387 WALK_SUBTREES is part of the walk_tree api but is unused here.
388 DATA is cgraph_node of the function being walked. */
390 /* FIXME: When this is converted to run over SSA form, this code
391 should be converted to use the operand scanner. */
394 scan_function (tree
*tp
,
398 struct cgraph_node
*fn
= (struct cgraph_node
*) data
;
400 funct_state local
= get_function_state (fn
);
402 switch (TREE_CODE (t
))
405 if (DECL_INITIAL (t
))
406 walk_tree (&DECL_INITIAL (t
), scan_function
, fn
, visited_nodes
);
410 case GIMPLE_MODIFY_STMT
:
412 /* First look on the lhs and see what variable is stored to */
413 tree lhs
= GIMPLE_STMT_OPERAND (t
, 0);
414 tree rhs
= GIMPLE_STMT_OPERAND (t
, 1);
415 check_lhs_var (local
, lhs
);
417 /* For the purposes of figuring out what the cast affects */
419 /* Next check the operands on the rhs to see if they are ok. */
420 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
424 tree op0
= TREE_OPERAND (rhs
, 0);
425 tree op1
= TREE_OPERAND (rhs
, 1);
426 check_rhs_var (local
, op0
);
427 check_rhs_var (local
, op1
);
432 tree op0
= TREE_OPERAND (rhs
, 0);
433 check_rhs_var (local
, op0
);
438 check_rhs_var (local
, rhs
);
440 case tcc_declaration
:
441 check_rhs_var (local
, rhs
);
444 switch (TREE_CODE (rhs
))
447 check_rhs_var (local
, rhs
);
454 switch (TREE_CODE (rhs
))
457 check_call (local
, rhs
);
471 /* This case is here to find addresses on rhs of constructors in
472 decl_initial of static variables. */
473 check_rhs_var (local
, t
);
478 if (DECL_NONLOCAL (TREE_OPERAND (t
, 0)))
479 /* Target of long jump. */
480 local
->pure_const_state
= IPA_NEITHER
;
484 check_call (local
, t
);
489 get_asm_expr_operands (local
, t
);
499 /* This is the main routine for finding the reference patterns for
500 global variables within a function FN. */
503 analyze_function (struct cgraph_node
*fn
)
505 funct_state l
= XCNEW (struct funct_state_d
);
506 tree decl
= fn
->decl
;
507 struct ipa_dfs_info
* w_info
= (struct ipa_dfs_info
*) fn
->aux
;
511 l
->pure_const_state
= IPA_CONST
;
512 l
->state_set_in_source
= false;
514 /* If this function does not return normally or does not bind local,
515 do not touch this unless it has been marked as const or pure by the
517 if (TREE_THIS_VOLATILE (decl
)
518 || !targetm
.binds_local_p (decl
))
520 l
->pure_const_state
= IPA_NEITHER
;
524 if (TREE_READONLY (decl
))
526 l
->pure_const_state
= IPA_CONST
;
527 l
->state_set_in_source
= true;
529 if (DECL_IS_PURE (decl
))
531 l
->pure_const_state
= IPA_PURE
;
532 l
->state_set_in_source
= true;
537 fprintf (dump_file
, "\n local analysis of %s with initial value = %d\n ",
538 cgraph_node_name (fn
),
539 l
->pure_const_state
);
542 if (!l
->state_set_in_source
)
544 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (decl
);
545 basic_block this_block
;
547 FOR_EACH_BB_FN (this_block
, this_cfun
)
549 block_stmt_iterator bsi
;
550 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
552 walk_tree (bsi_stmt_ptr (bsi
), scan_function
,
554 if (l
->pure_const_state
== IPA_NEITHER
)
559 if (l
->pure_const_state
!= IPA_NEITHER
)
561 tree old_decl
= current_function_decl
;
562 /* Const functions cannot have back edges (an
563 indication of possible infinite loop side
566 current_function_decl
= fn
->decl
;
568 /* The C++ front end, has a tendency to some times jerk away
569 a function after it has created it. This should have
571 gcc_assert (DECL_STRUCT_FUNCTION (fn
->decl
));
573 push_cfun (DECL_STRUCT_FUNCTION (fn
->decl
));
575 if (mark_dfs_back_edges ())
576 l
->pure_const_state
= IPA_NEITHER
;
578 current_function_decl
= old_decl
;
586 fprintf (dump_file
, "after local analysis of %s with initial value = %d\n ",
587 cgraph_node_name (fn
),
588 l
->pure_const_state
);
593 /* Produce the global information by preforming a transitive closure
594 on the local information that was produced by ipa_analyze_function
595 and ipa_analyze_variable. */
598 static_execute (void)
600 struct cgraph_node
*node
;
601 struct cgraph_node
*w
;
602 struct cgraph_node
**order
=
603 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
604 int order_pos
= ipa_utils_reduced_inorder (order
, true, false);
606 struct ipa_dfs_info
* w_info
;
608 if (!memory_identifier_string
)
609 memory_identifier_string
= build_string(7, "memory");
611 /* There are some shared nodes, in particular the initializers on
612 static declarations. We do not need to scan them more than once
613 since all we would be interested in are the addressof
615 visited_nodes
= pointer_set_create ();
617 /* Process all of the functions.
619 We do not want to process any of the clones so we check that this
620 is a master clone. However, we do NOT process any
621 AVAIL_OVERWRITABLE functions (these are never clones) we cannot
622 guarantee that what we learn about the one we see will be true
623 for the one that overriders it.
625 for (node
= cgraph_nodes
; node
; node
= node
->next
)
626 if (node
->analyzed
&& cgraph_is_master_clone (node
))
627 analyze_function (node
);
629 pointer_set_destroy (visited_nodes
);
630 visited_nodes
= NULL
;
633 dump_cgraph (dump_file
);
634 ipa_utils_print_order(dump_file
, "reduced", order
, order_pos
);
637 /* Propagate the local information thru the call graph to produce
638 the global information. All the nodes within a cycle will have
639 the same info so we collapse cycles first. Then we can do the
640 propagation in one pass from the leaves to the roots. */
641 for (i
= 0; i
< order_pos
; i
++ )
643 enum pure_const_state_e pure_const_state
= IPA_CONST
;
646 /* Find the worst state for any node in the cycle. */
650 funct_state w_l
= get_function_state (w
);
651 if (pure_const_state
< w_l
->pure_const_state
)
652 pure_const_state
= w_l
->pure_const_state
;
654 if (pure_const_state
== IPA_NEITHER
)
657 if (!w_l
->state_set_in_source
)
659 struct cgraph_edge
*e
;
660 for (e
= w
->callees
; e
; e
= e
->next_callee
)
662 struct cgraph_node
*y
= e
->callee
;
663 /* Only look at the master nodes and skip external nodes. */
664 y
= cgraph_master_clone (y
);
667 funct_state y_l
= get_function_state (y
);
668 if (pure_const_state
< y_l
->pure_const_state
)
669 pure_const_state
= y_l
->pure_const_state
;
670 if (pure_const_state
== IPA_NEITHER
)
675 w_info
= (struct ipa_dfs_info
*) w
->aux
;
676 w
= w_info
->next_cycle
;
679 /* Copy back the region's pure_const_state which is shared by
680 all nodes in the region. */
684 funct_state w_l
= get_function_state (w
);
686 /* All nodes within a cycle share the same info. */
687 if (!w_l
->state_set_in_source
)
689 w_l
->pure_const_state
= pure_const_state
;
690 switch (pure_const_state
)
693 TREE_READONLY (w
->decl
) = 1;
695 fprintf (dump_file
, "Function found to be const: %s\n",
696 lang_hooks
.decl_printable_name(w
->decl
, 2));
700 DECL_IS_PURE (w
->decl
) = 1;
702 fprintf (dump_file
, "Function found to be pure: %s\n",
703 lang_hooks
.decl_printable_name(w
->decl
, 2));
710 w_info
= (struct ipa_dfs_info
*) w
->aux
;
711 w
= w_info
->next_cycle
;
716 for (node
= cgraph_nodes
; node
; node
= node
->next
)
717 /* Get rid of the aux information. */
720 w_info
= (struct ipa_dfs_info
*) node
->aux
;
732 gate_pure_const (void)
734 return (flag_unit_at_a_time
!= 0 && flag_ipa_pure_const
735 /* Don't bother doing anything if the program has errors. */
736 && !(errorcount
|| sorrycount
));
739 struct tree_opt_pass pass_ipa_pure_const
=
741 "pure-const", /* name */
742 gate_pure_const
, /* gate */
743 static_execute
, /* execute */
746 0, /* static_pass_number */
747 TV_IPA_PURE_CONST
, /* tv_id */
748 0, /* properties_required */
749 0, /* properties_provided */
750 0, /* properties_destroyed */
751 0, /* todo_flags_start */
752 0, /* todo_flags_finish */