Daily bump.
[official-gcc.git] / gcc / ipa-pure-const.c
blobeb4262a0047bcbe9b81c356c574795c3176a2e61
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
10 version.
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
15 for more details.
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
22 pure (DECL_IS_PURE).
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. */
33 #include "config.h"
34 #include "system.h"
35 #include "coretypes.h"
36 #include "tm.h"
37 #include "tree.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"
43 #include "ggc.h"
44 #include "ipa-utils.h"
45 #include "c-common.h"
46 #include "tree-gimple.h"
47 #include "cgraph.h"
48 #include "output.h"
49 #include "flags.h"
50 #include "timevar.h"
51 #include "diagnostic.h"
52 #include "langhooks.h"
53 #include "target.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
59 what is found. */
60 enum pure_const_state_e
62 IPA_CONST,
63 IPA_PURE,
64 IPA_NEITHER
67 /* Holder inserted into the ipa_dfs_info aux field to hold the
68 const_state. */
69 struct funct_state_d
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. */
89 static inline void
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;
98 return;
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;
106 return;
109 /* Do not care about a local automatic that is not static. */
110 if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
111 return;
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
115 function. */
116 if (checking_write)
118 local->pure_const_state = IPA_NEITHER;
119 return;
122 if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
124 /* If the front end set the variable to be READONLY and
125 constant, we can allow this variable in pure or const
126 functions but the scope is too large for our analysis to set
127 these bits ourselves. */
129 if (TREE_READONLY (t)
130 && DECL_INITIAL (t)
131 && is_gimple_min_invariant (DECL_INITIAL (t)))
132 ; /* Read of a constant, do not change the function state. */
133 else
135 /* Just a regular read. */
136 if (local->pure_const_state == IPA_CONST)
137 local->pure_const_state = IPA_PURE;
141 /* Compilation level statics can be read if they are readonly
142 variables. */
143 if (TREE_READONLY (t))
144 return;
146 /* Just a regular read. */
147 if (local->pure_const_state == IPA_CONST)
148 local->pure_const_state = IPA_PURE;
151 /* If T is a VAR_DECL check to see if it is an allowed reference. */
153 static void
154 check_operand (funct_state local,
155 tree t, bool checking_write)
157 if (!t) return;
159 if (TREE_CODE (t) == VAR_DECL)
160 check_decl (local, t, checking_write);
163 /* Examine tree T for references. */
165 static void
166 check_tree (funct_state local, tree t, bool checking_write)
168 if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)
169 || TREE_CODE (t) == SSA_NAME)
170 return;
172 /* Any tree which is volatile disqualifies thie function from being
173 const or pure. */
174 if (TREE_THIS_VOLATILE (t))
176 local->pure_const_state = IPA_NEITHER;
177 return;
180 while (TREE_CODE (t) == REALPART_EXPR
181 || TREE_CODE (t) == IMAGPART_EXPR
182 || handled_component_p (t))
184 if (TREE_CODE (t) == ARRAY_REF)
185 check_operand (local, TREE_OPERAND (t, 1), false);
186 t = TREE_OPERAND (t, 0);
189 /* The bottom of an indirect reference can only be read, not
190 written. */
191 if (INDIRECT_REF_P (t))
193 check_tree (local, TREE_OPERAND (t, 0), false);
195 /* Any indirect reference that occurs on the lhs
196 disqualifies the function from being pure or const. Any
197 indirect reference that occurs on the rhs disqualifies the
198 function from being const. */
199 if (checking_write)
201 local->pure_const_state = IPA_NEITHER;
202 return;
204 else if (local->pure_const_state == IPA_CONST)
205 local->pure_const_state = IPA_PURE;
208 if (SSA_VAR_P (t))
209 check_operand (local, t, checking_write);
212 /* Scan tree T to see if there are any addresses taken in within T. */
214 static void
215 look_for_address_of (funct_state local, tree t)
217 if (TREE_CODE (t) == ADDR_EXPR)
219 tree x = get_base_var (t);
220 if (TREE_CODE (x) == VAR_DECL)
222 check_decl (local, x, false);
224 /* Taking the address of something appears to be reasonable
225 in PURE code. Not allowed in const. */
226 if (local->pure_const_state == IPA_CONST)
227 local->pure_const_state = IPA_PURE;
232 /* Check to see if T is a read or address of operation on a var we are
233 interested in analyzing. LOCAL is passed in to get access to its
234 bit vectors. */
236 static void
237 check_rhs_var (funct_state local, tree t)
239 look_for_address_of (local, t);
241 /* Memcmp and strlen can both trap and they are declared pure. */
242 if (tree_could_trap_p (t)
243 && local->pure_const_state == IPA_CONST)
244 local->pure_const_state = IPA_PURE;
246 check_tree(local, t, false);
249 /* Check to see if T is an assignment to a var we are interested in
250 analyzing. LOCAL is passed in to get access to its bit vectors. */
252 static void
253 check_lhs_var (funct_state local, tree t)
255 /* Memcmp and strlen can both trap and they are declared pure.
256 Which seems to imply that we can apply the same rule here. */
257 if (tree_could_trap_p (t)
258 && local->pure_const_state == IPA_CONST)
259 local->pure_const_state = IPA_PURE;
261 check_tree(local, t, true);
264 /* This is a scaled down version of get_asm_expr_operands from
265 tree_ssa_operands.c. The version there runs much later and assumes
266 that aliasing information is already available. Here we are just
267 trying to find if the set of inputs and outputs contain references
268 or address of operations to local static variables. STMT is the
269 actual asm statement. */
271 static void
272 get_asm_expr_operands (funct_state local, tree stmt)
274 int noutputs = list_length (ASM_OUTPUTS (stmt));
275 const char **oconstraints
276 = (const char **) alloca ((noutputs) * sizeof (const char *));
277 int i;
278 tree link;
279 const char *constraint;
280 bool allows_mem, allows_reg, is_inout;
282 for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link))
284 oconstraints[i] = constraint
285 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
286 parse_output_constraint (&constraint, i, 0, 0,
287 &allows_mem, &allows_reg, &is_inout);
289 check_lhs_var (local, TREE_VALUE (link));
292 for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
294 constraint
295 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
296 parse_input_constraint (&constraint, 0, 0, noutputs, 0,
297 oconstraints, &allows_mem, &allows_reg);
299 check_rhs_var (local, TREE_VALUE (link));
302 for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link))
303 if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1)
304 /* Abandon all hope, ye who enter here. */
305 local->pure_const_state = IPA_NEITHER;
307 if (ASM_VOLATILE_P (stmt))
308 local->pure_const_state = IPA_NEITHER;
311 /* Check the parameters of a function call to CALL_EXPR to see if
312 there are any references in the parameters that are not allowed for
313 pure or const functions. Also check to see if this is either an
314 indirect call, a call outside the compilation unit, or has special
315 attributes that may also effect the purity. The CALL_EXPR node for
316 the entire call expression. */
318 static void
319 check_call (funct_state local, tree call_expr)
321 int flags = call_expr_flags (call_expr);
322 tree operand;
323 call_expr_arg_iterator iter;
324 tree callee_t = get_callee_fndecl (call_expr);
325 struct cgraph_node* callee;
326 enum availability avail = AVAIL_NOT_AVAILABLE;
328 FOR_EACH_CALL_EXPR_ARG (operand, iter, call_expr)
329 check_rhs_var (local, operand);
331 /* The const and pure flags are set by a variety of places in the
332 compiler (including here). If someone has already set the flags
333 for the callee, (such as for some of the builtins) we will use
334 them, otherwise we will compute our own information.
336 Const and pure functions have less clobber effects than other
337 functions so we process these first. Otherwise if it is a call
338 outside the compilation unit or an indirect call we punt. This
339 leaves local calls which will be processed by following the call
340 graph. */
341 if (callee_t)
343 callee = cgraph_node(callee_t);
344 avail = cgraph_function_body_availability (callee);
346 /* When bad things happen to bad functions, they cannot be const
347 or pure. */
348 if (setjmp_call_p (callee_t))
349 local->pure_const_state = IPA_NEITHER;
351 if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
352 switch (DECL_FUNCTION_CODE (callee_t))
354 case BUILT_IN_LONGJMP:
355 case BUILT_IN_NONLOCAL_GOTO:
356 local->pure_const_state = IPA_NEITHER;
357 break;
358 default:
359 break;
363 /* The callee is either unknown (indirect call) or there is just no
364 scannable code for it (external call) . We look to see if there
365 are any bits available for the callee (such as by declaration or
366 because it is builtin) and process solely on the basis of those
367 bits. */
368 if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
370 if (flags & ECF_PURE)
372 if (local->pure_const_state == IPA_CONST)
373 local->pure_const_state = IPA_PURE;
375 else
376 local->pure_const_state = IPA_NEITHER;
378 else
380 /* We have the code and we will scan it for the effects. */
381 if (flags & ECF_PURE)
383 if (local->pure_const_state == IPA_CONST)
384 local->pure_const_state = IPA_PURE;
389 /* TP is the part of the tree currently under the microscope.
390 WALK_SUBTREES is part of the walk_tree api but is unused here.
391 DATA is cgraph_node of the function being walked. */
393 /* FIXME: When this is converted to run over SSA form, this code
394 should be converted to use the operand scanner. */
396 static tree
397 scan_function (tree *tp,
398 int *walk_subtrees,
399 void *data)
401 struct cgraph_node *fn = (struct cgraph_node *) data;
402 tree t = *tp;
403 funct_state local = get_function_state (fn);
405 switch (TREE_CODE (t))
407 case VAR_DECL:
408 if (DECL_INITIAL (t))
409 walk_tree (&DECL_INITIAL (t), scan_function, fn, visited_nodes);
410 *walk_subtrees = 0;
411 break;
413 case GIMPLE_MODIFY_STMT:
415 /* First look on the lhs and see what variable is stored to */
416 tree lhs = GIMPLE_STMT_OPERAND (t, 0);
417 tree rhs = GIMPLE_STMT_OPERAND (t, 1);
418 check_lhs_var (local, lhs);
420 /* For the purposes of figuring out what the cast affects */
422 /* Next check the operands on the rhs to see if they are ok. */
423 switch (TREE_CODE_CLASS (TREE_CODE (rhs)))
425 case tcc_binary:
427 tree op0 = TREE_OPERAND (rhs, 0);
428 tree op1 = TREE_OPERAND (rhs, 1);
429 check_rhs_var (local, op0);
430 check_rhs_var (local, op1);
432 break;
433 case tcc_unary:
435 tree op0 = TREE_OPERAND (rhs, 0);
436 check_rhs_var (local, op0);
439 break;
440 case tcc_reference:
441 check_rhs_var (local, rhs);
442 break;
443 case tcc_declaration:
444 check_rhs_var (local, rhs);
445 break;
446 case tcc_expression:
447 switch (TREE_CODE (rhs))
449 case ADDR_EXPR:
450 check_rhs_var (local, rhs);
451 break;
452 default:
453 break;
455 break;
456 case tcc_vl_exp:
457 switch (TREE_CODE (rhs))
459 case CALL_EXPR:
460 check_call (local, rhs);
461 break;
462 default:
463 break;
465 break;
466 default:
467 break;
469 *walk_subtrees = 0;
471 break;
473 case ADDR_EXPR:
474 /* This case is here to find addresses on rhs of constructors in
475 decl_initial of static variables. */
476 check_rhs_var (local, t);
477 *walk_subtrees = 0;
478 break;
480 case LABEL_EXPR:
481 if (DECL_NONLOCAL (TREE_OPERAND (t, 0)))
482 /* Target of long jump. */
483 local->pure_const_state = IPA_NEITHER;
484 break;
486 case CALL_EXPR:
487 check_call (local, t);
488 *walk_subtrees = 0;
489 break;
491 case ASM_EXPR:
492 get_asm_expr_operands (local, t);
493 *walk_subtrees = 0;
494 break;
496 default:
497 break;
499 return NULL;
502 /* This is the main routine for finding the reference patterns for
503 global variables within a function FN. */
505 static void
506 analyze_function (struct cgraph_node *fn)
508 funct_state l = XCNEW (struct funct_state_d);
509 tree decl = fn->decl;
510 struct ipa_dfs_info * w_info = (struct ipa_dfs_info *) fn->aux;
512 w_info->aux = l;
514 l->pure_const_state = IPA_CONST;
515 l->state_set_in_source = false;
517 /* If this function does not return normally or does not bind local,
518 do not touch this unless it has been marked as const or pure by the
519 front end. */
520 if (TREE_THIS_VOLATILE (decl)
521 || !targetm.binds_local_p (decl))
523 l->pure_const_state = IPA_NEITHER;
524 return;
527 if (TREE_READONLY (decl))
529 l->pure_const_state = IPA_CONST;
530 l->state_set_in_source = true;
532 if (DECL_IS_PURE (decl))
534 l->pure_const_state = IPA_PURE;
535 l->state_set_in_source = true;
538 if (dump_file)
540 fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ",
541 cgraph_node_name (fn),
542 l->pure_const_state);
545 if (!l->state_set_in_source)
547 struct function *this_cfun = DECL_STRUCT_FUNCTION (decl);
548 basic_block this_block;
550 FOR_EACH_BB_FN (this_block, this_cfun)
552 block_stmt_iterator bsi;
553 for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi))
555 walk_tree (bsi_stmt_ptr (bsi), scan_function,
556 fn, visited_nodes);
557 if (l->pure_const_state == IPA_NEITHER)
558 goto end;
562 if (l->pure_const_state != IPA_NEITHER)
564 tree old_decl = current_function_decl;
565 /* Const functions cannot have back edges (an
566 indication of possible infinite loop side
567 effect. */
569 current_function_decl = fn->decl;
571 /* The C++ front end, has a tendency to some times jerk away
572 a function after it has created it. This should have
573 been fixed. */
574 gcc_assert (DECL_STRUCT_FUNCTION (fn->decl));
576 push_cfun (DECL_STRUCT_FUNCTION (fn->decl));
578 if (mark_dfs_back_edges ())
579 l->pure_const_state = IPA_NEITHER;
581 current_function_decl = old_decl;
582 pop_cfun ();
586 end:
587 if (dump_file)
589 fprintf (dump_file, "after local analysis of %s with initial value = %d\n ",
590 cgraph_node_name (fn),
591 l->pure_const_state);
596 /* Produce the global information by preforming a transitive closure
597 on the local information that was produced by ipa_analyze_function
598 and ipa_analyze_variable. */
600 static unsigned int
601 static_execute (void)
603 struct cgraph_node *node;
604 struct cgraph_node *w;
605 struct cgraph_node **order =
606 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
607 int order_pos = ipa_utils_reduced_inorder (order, true, false);
608 int i;
609 struct ipa_dfs_info * w_info;
611 if (!memory_identifier_string)
612 memory_identifier_string = build_string(7, "memory");
614 /* There are some shared nodes, in particular the initializers on
615 static declarations. We do not need to scan them more than once
616 since all we would be interested in are the addressof
617 operations. */
618 visited_nodes = pointer_set_create ();
620 /* Process all of the functions.
622 We do not want to process any of the clones so we check that this
623 is a master clone. However, we do NOT process any
624 AVAIL_OVERWRITABLE functions (these are never clones) we cannot
625 guarantee that what we learn about the one we see will be true
626 for the one that overriders it.
628 for (node = cgraph_nodes; node; node = node->next)
629 if (node->analyzed && cgraph_is_master_clone (node))
630 analyze_function (node);
632 pointer_set_destroy (visited_nodes);
633 visited_nodes = NULL;
634 if (dump_file)
636 dump_cgraph (dump_file);
637 ipa_utils_print_order(dump_file, "reduced", order, order_pos);
640 /* Propagate the local information thru the call graph to produce
641 the global information. All the nodes within a cycle will have
642 the same info so we collapse cycles first. Then we can do the
643 propagation in one pass from the leaves to the roots. */
644 for (i = 0; i < order_pos; i++ )
646 enum pure_const_state_e pure_const_state = IPA_CONST;
647 int count = 0;
648 node = order[i];
650 /* Find the worst state for any node in the cycle. */
651 w = node;
652 while (w)
654 funct_state w_l = get_function_state (w);
655 if (pure_const_state < w_l->pure_const_state)
656 pure_const_state = w_l->pure_const_state;
658 if (pure_const_state == IPA_NEITHER)
659 break;
661 if (!w_l->state_set_in_source)
663 struct cgraph_edge *e;
664 count++;
666 /* FIXME!!! Because of pr33826, we cannot have either
667 immediate or transitive recursive functions marked as
668 pure or const because dce can delete a function that
669 is in reality an infinite loop. A better solution
670 than just outlawing them is to add another bit the
671 functions to distinguish recursive from non recursive
672 pure and const function. This would allow the
673 recursive ones to be cse'd but not dce'd. In this
674 same vein, we could allow functions with loops to
675 also be cse'd but not dce'd.
677 Unfortunately we are late in stage 3, and the fix
678 described above is is not appropriate. */
679 if (count > 1)
681 pure_const_state = IPA_NEITHER;
682 break;
685 for (e = w->callees; e; e = e->next_callee)
687 struct cgraph_node *y = e->callee;
688 /* Only look at the master nodes and skip external nodes. */
689 y = cgraph_master_clone (y);
691 /* Check for immediate recursive functions. See the
692 FIXME above. */
693 if (w == y)
695 pure_const_state = IPA_NEITHER;
696 break;
698 if (y)
700 funct_state y_l = get_function_state (y);
701 if (pure_const_state < y_l->pure_const_state)
702 pure_const_state = y_l->pure_const_state;
703 if (pure_const_state == IPA_NEITHER)
704 break;
708 w_info = (struct ipa_dfs_info *) w->aux;
709 w = w_info->next_cycle;
712 /* Copy back the region's pure_const_state which is shared by
713 all nodes in the region. */
714 w = node;
715 while (w)
717 funct_state w_l = get_function_state (w);
719 /* All nodes within a cycle share the same info. */
720 if (!w_l->state_set_in_source)
722 w_l->pure_const_state = pure_const_state;
723 switch (pure_const_state)
725 case IPA_CONST:
726 TREE_READONLY (w->decl) = 1;
727 if (dump_file)
728 fprintf (dump_file, "Function found to be const: %s\n",
729 lang_hooks.decl_printable_name(w->decl, 2));
730 break;
732 case IPA_PURE:
733 DECL_IS_PURE (w->decl) = 1;
734 if (dump_file)
735 fprintf (dump_file, "Function found to be pure: %s\n",
736 lang_hooks.decl_printable_name(w->decl, 2));
737 break;
739 default:
740 break;
743 w_info = (struct ipa_dfs_info *) w->aux;
744 w = w_info->next_cycle;
748 /* Cleanup. */
749 for (node = cgraph_nodes; node; node = node->next)
750 /* Get rid of the aux information. */
751 if (node->aux)
753 w_info = (struct ipa_dfs_info *) node->aux;
754 if (w_info->aux)
755 free (w_info->aux);
756 free (node->aux);
757 node->aux = NULL;
760 free (order);
761 return 0;
764 static bool
765 gate_pure_const (void)
767 return (flag_unit_at_a_time != 0 && flag_ipa_pure_const
768 /* Don't bother doing anything if the program has errors. */
769 && !(errorcount || sorrycount));
772 struct tree_opt_pass pass_ipa_pure_const =
774 "pure-const", /* name */
775 gate_pure_const, /* gate */
776 static_execute, /* execute */
777 NULL, /* sub */
778 NULL, /* next */
779 0, /* static_pass_number */
780 TV_IPA_PURE_CONST, /* tv_id */
781 0, /* properties_required */
782 0, /* properties_provided */
783 0, /* properties_destroyed */
784 0, /* todo_flags_start */
785 0, /* todo_flags_finish */
786 0 /* letter */