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
= node
->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
))
168 /* Any tree which is volatile disqualifies thie function from being
170 if (TREE_THIS_VOLATILE (t
))
172 local
->pure_const_state
= IPA_NEITHER
;
176 while (TREE_CODE (t
) == REALPART_EXPR
177 || TREE_CODE (t
) == IMAGPART_EXPR
178 || handled_component_p (t
))
180 if (TREE_CODE (t
) == ARRAY_REF
)
181 check_operand (local
, TREE_OPERAND (t
, 1), false);
182 t
= TREE_OPERAND (t
, 0);
185 /* The bottom of an indirect reference can only be read, not
187 if (INDIRECT_REF_P (t
))
189 check_tree (local
, TREE_OPERAND (t
, 0), false);
191 /* Any indirect reference that occurs on the lhs
192 disqualifies the function from being pure or const. Any
193 indirect reference that occurs on the rhs disqualifies the
194 function from being const. */
197 local
->pure_const_state
= IPA_NEITHER
;
200 else if (local
->pure_const_state
== IPA_CONST
)
201 local
->pure_const_state
= IPA_PURE
;
205 check_operand (local
, t
, checking_write
);
208 /* Scan tree T to see if there are any addresses taken in within T. */
211 look_for_address_of (funct_state local
, tree t
)
213 if (TREE_CODE (t
) == ADDR_EXPR
)
215 tree x
= get_base_var (t
);
216 if (TREE_CODE (x
) == VAR_DECL
)
218 check_decl (local
, x
, false);
220 /* Taking the address of something appears to be reasonable
221 in PURE code. Not allowed in const. */
222 if (local
->pure_const_state
== IPA_CONST
)
223 local
->pure_const_state
= IPA_PURE
;
228 /* Check to see if T is a read or address of operation on a var we are
229 interested in analyzing. LOCAL is passed in to get access to its
233 check_rhs_var (funct_state local
, tree t
)
235 look_for_address_of (local
, t
);
237 /* Memcmp and strlen can both trap and they are declared pure. */
238 if (tree_could_trap_p (t
)
239 && local
->pure_const_state
== IPA_CONST
)
240 local
->pure_const_state
= IPA_PURE
;
242 check_tree(local
, t
, false);
245 /* Check to see if T is an assignment to a var we are interested in
246 analyzing. LOCAL is passed in to get access to its bit vectors. */
249 check_lhs_var (funct_state local
, tree t
)
251 /* Memcmp and strlen can both trap and they are declared pure.
252 Which seems to imply that we can apply the same rule here. */
253 if (tree_could_trap_p (t
)
254 && local
->pure_const_state
== IPA_CONST
)
255 local
->pure_const_state
= IPA_PURE
;
257 check_tree(local
, t
, true);
260 /* This is a scaled down version of get_asm_expr_operands from
261 tree_ssa_operands.c. The version there runs much later and assumes
262 that aliasing information is already available. Here we are just
263 trying to find if the set of inputs and outputs contain references
264 or address of operations to local static variables. STMT is the
265 actual asm statement. */
268 get_asm_expr_operands (funct_state local
, tree stmt
)
270 int noutputs
= list_length (ASM_OUTPUTS (stmt
));
271 const char **oconstraints
272 = (const char **) alloca ((noutputs
) * sizeof (const char *));
275 const char *constraint
;
276 bool allows_mem
, allows_reg
, is_inout
;
278 for (i
=0, link
= ASM_OUTPUTS (stmt
); link
; ++i
, link
= TREE_CHAIN (link
))
280 oconstraints
[i
] = constraint
281 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
282 parse_output_constraint (&constraint
, i
, 0, 0,
283 &allows_mem
, &allows_reg
, &is_inout
);
285 check_lhs_var (local
, TREE_VALUE (link
));
288 for (link
= ASM_INPUTS (stmt
); link
; link
= TREE_CHAIN (link
))
291 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link
)));
292 parse_input_constraint (&constraint
, 0, 0, noutputs
, 0,
293 oconstraints
, &allows_mem
, &allows_reg
);
295 check_rhs_var (local
, TREE_VALUE (link
));
298 for (link
= ASM_CLOBBERS (stmt
); link
; link
= TREE_CHAIN (link
))
299 if (simple_cst_equal(TREE_VALUE (link
), memory_identifier_string
) == 1)
300 /* Abandon all hope, ye who enter here. */
301 local
->pure_const_state
= IPA_NEITHER
;
303 if (ASM_VOLATILE_P (stmt
))
304 local
->pure_const_state
= IPA_NEITHER
;
307 /* Check the parameters of a function call to CALL_EXPR to see if
308 there are any references in the parameters that are not allowed for
309 pure or const functions. Also check to see if this is either an
310 indirect call, a call outside the compilation unit, or has special
311 attributes that may also effect the purity. The CALL_EXPR node for
312 the entire call expression. */
315 check_call (funct_state local
, tree call_expr
)
317 int flags
= call_expr_flags(call_expr
);
318 tree operand_list
= TREE_OPERAND (call_expr
, 1);
320 tree callee_t
= get_callee_fndecl (call_expr
);
321 struct cgraph_node
* callee
;
322 enum availability avail
= AVAIL_NOT_AVAILABLE
;
324 for (operand
= operand_list
;
325 operand
!= NULL_TREE
;
326 operand
= TREE_CHAIN (operand
))
328 tree argument
= TREE_VALUE (operand
);
329 check_rhs_var (local
, argument
);
332 /* The const and pure flags are set by a variety of places in the
333 compiler (including here). If someone has already set the flags
334 for the callee, (such as for some of the builtins) we will use
335 them, otherwise we will compute our own information.
337 Const and pure functions have less clobber effects than other
338 functions so we process these first. Otherwise if it is a call
339 outside the compilation unit or an indirect call we punt. This
340 leaves local calls which will be processed by following the call
344 callee
= cgraph_node(callee_t
);
345 avail
= cgraph_function_body_availability (callee
);
347 /* When bad things happen to bad functions, they cannot be const
349 if (setjmp_call_p (callee_t
))
350 local
->pure_const_state
= IPA_NEITHER
;
352 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
353 switch (DECL_FUNCTION_CODE (callee_t
))
355 case BUILT_IN_LONGJMP
:
356 case BUILT_IN_NONLOCAL_GOTO
:
357 local
->pure_const_state
= IPA_NEITHER
;
364 /* The callee is either unknown (indirect call) or there is just no
365 scannable code for it (external call) . We look to see if there
366 are any bits available for the callee (such as by declaration or
367 because it is builtin) and process solely on the basis of those
369 if (avail
== AVAIL_NOT_AVAILABLE
|| avail
== AVAIL_OVERWRITABLE
)
371 if (flags
& ECF_PURE
)
373 if (local
->pure_const_state
== IPA_CONST
)
374 local
->pure_const_state
= IPA_PURE
;
377 local
->pure_const_state
= IPA_NEITHER
;
381 /* We have the code and we will scan it for the effects. */
382 if (flags
& ECF_PURE
)
384 if (local
->pure_const_state
== IPA_CONST
)
385 local
->pure_const_state
= IPA_PURE
;
390 /* TP is the part of the tree currently under the microscope.
391 WALK_SUBTREES is part of the walk_tree api but is unused here.
392 DATA is cgraph_node of the function being walked. */
394 /* FIXME: When this is converted to run over SSA form, this code
395 should be converted to use the operand scanner. */
398 scan_function (tree
*tp
,
402 struct cgraph_node
*fn
= data
;
404 funct_state local
= get_function_state (fn
);
406 switch (TREE_CODE (t
))
409 if (DECL_INITIAL (t
))
410 walk_tree (&DECL_INITIAL (t
), scan_function
, fn
, visited_nodes
);
416 /* First look on the lhs and see what variable is stored to */
417 tree lhs
= TREE_OPERAND (t
, 0);
418 tree rhs
= TREE_OPERAND (t
, 1);
419 check_lhs_var (local
, lhs
);
421 /* For the purposes of figuring out what the cast affects */
423 /* Next check the operands on the rhs to see if they are ok. */
424 switch (TREE_CODE_CLASS (TREE_CODE (rhs
)))
428 tree op0
= TREE_OPERAND (rhs
, 0);
429 tree op1
= TREE_OPERAND (rhs
, 1);
430 check_rhs_var (local
, op0
);
431 check_rhs_var (local
, op1
);
436 tree op0
= TREE_OPERAND (rhs
, 0);
437 check_rhs_var (local
, op0
);
442 check_rhs_var (local
, rhs
);
444 case tcc_declaration
:
445 check_rhs_var (local
, rhs
);
448 switch (TREE_CODE (rhs
))
451 check_rhs_var (local
, rhs
);
454 check_call (local
, rhs
);
468 /* This case is here to find addresses on rhs of constructors in
469 decl_initial of static variables. */
470 check_rhs_var (local
, t
);
475 if (DECL_NONLOCAL (TREE_OPERAND (t
, 0)))
476 /* Target of long jump. */
477 local
->pure_const_state
= IPA_NEITHER
;
481 check_call (local
, t
);
486 get_asm_expr_operands (local
, t
);
496 /* This is the main routine for finding the reference patterns for
497 global variables within a function FN. */
500 analyze_function (struct cgraph_node
*fn
)
502 funct_state l
= XCNEW (struct funct_state_d
);
503 tree decl
= fn
->decl
;
504 struct ipa_dfs_info
* w_info
= fn
->aux
;
508 l
->pure_const_state
= IPA_CONST
;
509 l
->state_set_in_source
= false;
511 /* If this function does not return normally or does not bind local,
512 do not touch this unless it has been marked as const or pure by the
514 if (TREE_THIS_VOLATILE (decl
)
515 || !targetm
.binds_local_p (decl
))
517 l
->pure_const_state
= IPA_NEITHER
;
521 if (TREE_READONLY (decl
))
523 l
->pure_const_state
= IPA_CONST
;
524 l
->state_set_in_source
= true;
526 if (DECL_IS_PURE (decl
))
528 l
->pure_const_state
= IPA_PURE
;
529 l
->state_set_in_source
= true;
534 fprintf (dump_file
, "\n local analysis of %s with initial value = %d\n ",
535 cgraph_node_name (fn
),
536 l
->pure_const_state
);
539 if (!l
->state_set_in_source
)
541 struct function
*this_cfun
= DECL_STRUCT_FUNCTION (decl
);
542 basic_block this_block
;
544 FOR_EACH_BB_FN (this_block
, this_cfun
)
546 block_stmt_iterator bsi
;
547 for (bsi
= bsi_start (this_block
); !bsi_end_p (bsi
); bsi_next (&bsi
))
549 walk_tree (bsi_stmt_ptr (bsi
), scan_function
,
551 if (l
->pure_const_state
== IPA_NEITHER
)
556 if (l
->pure_const_state
!= IPA_NEITHER
)
558 tree old_decl
= current_function_decl
;
559 /* Const functions cannot have back edges (an
560 indication of possible infinite loop side
563 current_function_decl
= fn
->decl
;
565 /* The C++ front end, has a tendency to some times jerk away
566 a function after it has created it. This should have
568 gcc_assert (DECL_STRUCT_FUNCTION (fn
->decl
));
570 push_cfun (DECL_STRUCT_FUNCTION (fn
->decl
));
572 if (mark_dfs_back_edges ())
573 l
->pure_const_state
= IPA_NEITHER
;
575 current_function_decl
= old_decl
;
583 fprintf (dump_file
, "after local analysis of %s with initial value = %d\n ",
584 cgraph_node_name (fn
),
585 l
->pure_const_state
);
590 /* Produce the global information by preforming a transitive closure
591 on the local information that was produced by ipa_analyze_function
592 and ipa_analyze_variable. */
595 static_execute (void)
597 struct cgraph_node
*node
;
598 struct cgraph_node
*w
;
599 struct cgraph_node
**order
=
600 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
601 int order_pos
= order_pos
= ipa_utils_reduced_inorder (order
, true, false);
603 struct ipa_dfs_info
* w_info
;
605 if (!memory_identifier_string
)
606 memory_identifier_string
= build_string(7, "memory");
608 /* There are some shared nodes, in particular the initializers on
609 static declarations. We do not need to scan them more than once
610 since all we would be interested in are the addressof
612 visited_nodes
= pointer_set_create ();
614 /* Process all of the functions.
616 We do not want to process any of the clones so we check that this
617 is a master clone. However, we do NOT process any
618 AVAIL_OVERWRITABLE functions (these are never clones) we cannot
619 guarantee that what we learn about the one we see will be true
620 for the one that overriders it.
622 for (node
= cgraph_nodes
; node
; node
= node
->next
)
623 if (node
->analyzed
&& cgraph_is_master_clone (node
))
624 analyze_function (node
);
626 pointer_set_destroy (visited_nodes
);
627 visited_nodes
= NULL
;
630 dump_cgraph (dump_file
);
631 ipa_utils_print_order(dump_file
, "reduced", order
, order_pos
);
634 /* Propagate the local information thru the call graph to produce
635 the global information. All the nodes within a cycle will have
636 the same info so we collapse cycles first. Then we can do the
637 propagation in one pass from the leaves to the roots. */
638 for (i
= 0; i
< order_pos
; i
++ )
640 enum pure_const_state_e pure_const_state
= IPA_CONST
;
644 /* Find the worst state for any node in the cycle. */
648 funct_state w_l
= get_function_state (w
);
649 if (pure_const_state
< w_l
->pure_const_state
)
650 pure_const_state
= w_l
->pure_const_state
;
652 if (pure_const_state
== IPA_NEITHER
)
655 if (!w_l
->state_set_in_source
)
657 struct cgraph_edge
*e
;
660 /* FIXME!!! Because of pr33826, we cannot have either
661 immediate or transitive recursive functions marked as
662 pure or const because dce can delete a function that
663 is in reality an infinite loop. A better solution
664 than just outlawing them is to add another bit the
665 functions to distinguish recursive from non recursive
666 pure and const function. This would allow the
667 recursive ones to be cse'd but not dce'd. In this
668 same vein, we could allow functions with loops to
669 also be cse'd but not dce'd.
671 Unfortunately we are late in stage 3, and the fix
672 described above is is not appropriate. */
675 pure_const_state
= IPA_NEITHER
;
679 for (e
= w
->callees
; e
; e
= e
->next_callee
)
681 struct cgraph_node
*y
= e
->callee
;
682 /* Only look at the master nodes and skip external nodes. */
683 y
= cgraph_master_clone (y
);
685 /* Check for immediate recursive functions. See the
689 pure_const_state
= IPA_NEITHER
;
694 funct_state y_l
= get_function_state (y
);
695 if (pure_const_state
< y_l
->pure_const_state
)
696 pure_const_state
= y_l
->pure_const_state
;
697 if (pure_const_state
== IPA_NEITHER
)
703 w
= w_info
->next_cycle
;
706 /* Copy back the region's pure_const_state which is shared by
707 all nodes in the region. */
711 funct_state w_l
= get_function_state (w
);
713 /* All nodes within a cycle share the same info. */
714 if (!w_l
->state_set_in_source
)
716 w_l
->pure_const_state
= pure_const_state
;
717 switch (pure_const_state
)
720 TREE_READONLY (w
->decl
) = 1;
722 fprintf (dump_file
, "Function found to be const: %s\n",
723 lang_hooks
.decl_printable_name(w
->decl
, 2));
727 DECL_IS_PURE (w
->decl
) = 1;
729 fprintf (dump_file
, "Function found to be pure: %s\n",
730 lang_hooks
.decl_printable_name(w
->decl
, 2));
738 w
= w_info
->next_cycle
;
743 for (node
= cgraph_nodes
; node
; node
= node
->next
)
744 /* Get rid of the aux information. */
759 gate_pure_const (void)
761 return (flag_unit_at_a_time
!= 0 && flag_ipa_pure_const
762 /* Don't bother doing anything if the program has errors. */
763 && !(errorcount
|| sorrycount
));
766 struct tree_opt_pass pass_ipa_pure_const
=
768 "pure-const", /* name */
769 gate_pure_const
, /* gate */
770 static_execute
, /* execute */
773 0, /* static_pass_number */
774 TV_IPA_PURE_CONST
, /* tv_id */
775 0, /* properties_required */
776 0, /* properties_provided */
777 0, /* properties_destroyed */
778 0, /* todo_flags_start */
779 0, /* todo_flags_finish */