1 /* Callgraph based analysis of static variables.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file marks functions as being either const (TREE_READONLY) or
23 pure (DECL_PURE_P). It can also set a variant of these that
24 are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P).
26 This must be run after inlining decisions have been made since
27 otherwise, the local sets will not contain information that is
28 consistent with post inlined state. The global sets are not prone
29 to this problem since they are by definition transitive. */
31 /* The code in this module is called by the ipa pass manager. It
32 should be one of the later passes since it's information is used by
33 the rest of the compilation. */
37 #include "coretypes.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "tree-pass.h"
43 #include "langhooks.h"
44 #include "pointer-set.h"
46 #include "ipa-utils.h"
53 #include "diagnostic.h"
54 #include "gimple-pretty-print.h"
55 #include "langhooks.h"
57 #include "lto-streamer.h"
59 #include "tree-scalar-evolution.h"
63 static struct pointer_set_t
*visited_nodes
;
65 /* Lattice values for const and pure functions. Everything starts out
66 being const, then may drop to pure and then neither depending on
68 enum pure_const_state_e
75 const char *pure_const_names
[3] = {"const", "pure", "neither"};
77 /* Holder for the const_state. There is one of these per function
82 enum pure_const_state_e pure_const_state
;
83 /* What user set here; we can be always sure about this. */
84 enum pure_const_state_e state_previously_known
;
85 bool looping_previously_known
;
87 /* True if the function could possibly infinite loop. There are a
88 lot of ways that this could be determined. We are pretty
89 conservative here. While it is possible to cse pure and const
90 calls, it is not legal to have dce get rid of the call if there
91 is a possibility that the call could infinite loop since this is
92 a behavioral change. */
98 typedef struct funct_state_d
* funct_state
;
100 /* The storage of the funct_state is abstracted because there is the
101 possibility that it may be desirable to move this to the cgraph
104 /* Array, indexed by cgraph node uid, of function states. */
106 DEF_VEC_P (funct_state
);
107 DEF_VEC_ALLOC_P (funct_state
, heap
);
108 static VEC (funct_state
, heap
) *funct_state_vec
;
110 /* Holders of ipa cgraph hooks: */
111 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
112 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
113 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
115 /* Try to guess if function body will always be visible to compiler
116 when compiling the call and whether compiler will be able
117 to propagate the information by itself. */
120 function_always_visible_to_compiler_p (tree decl
)
122 return (!TREE_PUBLIC (decl
) || DECL_DECLARED_INLINE_P (decl
));
125 /* Emit suggestion about attribute ATTRIB_NAME for DECL. KNOWN_FINITE
126 is true if the function is known to be finite. The diagnostic is
127 controlled by OPTION. WARNED_ABOUT is a pointer_set unique for
128 OPTION, this function may initialize it and it is always returned
131 static struct pointer_set_t
*
132 suggest_attribute (int option
, tree decl
, bool known_finite
,
133 struct pointer_set_t
*warned_about
,
134 const char * attrib_name
)
136 if (!option_enabled (option
))
138 if (TREE_THIS_VOLATILE (decl
)
139 || (known_finite
&& function_always_visible_to_compiler_p (decl
)))
143 warned_about
= pointer_set_create ();
144 if (pointer_set_contains (warned_about
, decl
))
146 pointer_set_insert (warned_about
, decl
);
147 warning_at (DECL_SOURCE_LOCATION (decl
),
150 ? _("function might be candidate for attribute %<%s%>")
151 : _("function might be candidate for attribute %<%s%>"
152 " if it is known to return normally"), attrib_name
);
156 /* Emit suggestion about __attribute_((pure)) for DECL. KNOWN_FINITE
157 is true if the function is known to be finite. */
160 warn_function_pure (tree decl
, bool known_finite
)
162 static struct pointer_set_t
*warned_about
;
165 = suggest_attribute (OPT_Wsuggest_attribute_pure
, decl
,
166 known_finite
, warned_about
, "pure");
169 /* Emit suggestion about __attribute_((const)) for DECL. KNOWN_FINITE
170 is true if the function is known to be finite. */
173 warn_function_const (tree decl
, bool known_finite
)
175 static struct pointer_set_t
*warned_about
;
177 = suggest_attribute (OPT_Wsuggest_attribute_const
, decl
,
178 known_finite
, warned_about
, "const");
182 warn_function_noreturn (tree decl
)
184 static struct pointer_set_t
*warned_about
;
185 if (!lang_hooks
.missing_noreturn_ok_p (decl
))
187 = suggest_attribute (OPT_Wsuggest_attribute_noreturn
, decl
,
188 true, warned_about
, "noreturn");
190 /* Init the function state. */
195 free (funct_state_vec
);
199 /* Return true if we have a function state for NODE. */
202 has_function_state (struct cgraph_node
*node
)
205 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
207 return VEC_index (funct_state
, funct_state_vec
, node
->uid
) != NULL
;
210 /* Return the function state from NODE. */
212 static inline funct_state
213 get_function_state (struct cgraph_node
*node
)
215 static struct funct_state_d varying
216 = { IPA_NEITHER
, IPA_NEITHER
, true, true, true };
218 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
219 /* We might want to put correct previously_known state into varying. */
221 return VEC_index (funct_state
, funct_state_vec
, node
->uid
);
224 /* Set the function state S for NODE. */
227 set_function_state (struct cgraph_node
*node
, funct_state s
)
230 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
231 VEC_safe_grow_cleared (funct_state
, heap
, funct_state_vec
, node
->uid
+ 1);
232 VEC_replace (funct_state
, funct_state_vec
, node
->uid
, s
);
235 /* Check to see if the use (or definition when CHECKING_WRITE is true)
236 variable T is legal in a function that is either pure or const. */
239 check_decl (funct_state local
,
240 tree t
, bool checking_write
, bool ipa
)
242 /* Do not want to do anything with volatile except mark any
243 function that uses one to be not const or pure. */
244 if (TREE_THIS_VOLATILE (t
))
246 local
->pure_const_state
= IPA_NEITHER
;
248 fprintf (dump_file
, " Volatile operand is not const/pure");
252 /* Do not care about a local automatic that is not static. */
253 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
256 /* If the variable has the "used" attribute, treat it as if it had a
257 been touched by the devil. */
258 if (DECL_PRESERVE_P (t
))
260 local
->pure_const_state
= IPA_NEITHER
;
262 fprintf (dump_file
, " Used static/global variable is not const/pure\n");
266 /* In IPA mode we are not interested in checking actual loads and stores;
267 they will be processed at propagation time using ipa_ref. */
271 /* Since we have dealt with the locals and params cases above, if we
272 are CHECKING_WRITE, this cannot be a pure or constant
276 local
->pure_const_state
= IPA_NEITHER
;
278 fprintf (dump_file
, " static/global memory write is not const/pure\n");
282 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
284 /* Readonly reads are safe. */
285 if (TREE_READONLY (t
) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t
)))
286 return; /* Read of a constant, do not change the function state. */
290 fprintf (dump_file
, " global memory read is not const\n");
291 /* Just a regular read. */
292 if (local
->pure_const_state
== IPA_CONST
)
293 local
->pure_const_state
= IPA_PURE
;
298 /* Compilation level statics can be read if they are readonly
300 if (TREE_READONLY (t
))
304 fprintf (dump_file
, " static memory read is not const\n");
305 /* Just a regular read. */
306 if (local
->pure_const_state
== IPA_CONST
)
307 local
->pure_const_state
= IPA_PURE
;
312 /* Check to see if the use (or definition when CHECKING_WRITE is true)
313 variable T is legal in a function that is either pure or const. */
316 check_op (funct_state local
, tree t
, bool checking_write
)
318 t
= get_base_address (t
);
319 if (t
&& TREE_THIS_VOLATILE (t
))
321 local
->pure_const_state
= IPA_NEITHER
;
323 fprintf (dump_file
, " Volatile indirect ref is not const/pure\n");
327 && (INDIRECT_REF_P (t
) || TREE_CODE (t
) == MEM_REF
)
328 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
329 && !ptr_deref_may_alias_global_p (TREE_OPERAND (t
, 0)))
332 fprintf (dump_file
, " Indirect ref to local memory is OK\n");
335 else if (checking_write
)
337 local
->pure_const_state
= IPA_NEITHER
;
339 fprintf (dump_file
, " Indirect ref write is not const/pure\n");
345 fprintf (dump_file
, " Indirect ref read is not const\n");
346 if (local
->pure_const_state
== IPA_CONST
)
347 local
->pure_const_state
= IPA_PURE
;
351 /* compute state based on ECF FLAGS and store to STATE and LOOPING. */
354 state_from_flags (enum pure_const_state_e
*state
, bool *looping
,
355 int flags
, bool cannot_lead_to_return
)
358 if (flags
& ECF_LOOPING_CONST_OR_PURE
)
361 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
362 fprintf (dump_file
, " looping");
364 if (flags
& ECF_CONST
)
367 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
368 fprintf (dump_file
, " const\n");
370 else if (flags
& ECF_PURE
)
373 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
374 fprintf (dump_file
, " pure\n");
376 else if (cannot_lead_to_return
)
380 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
381 fprintf (dump_file
, " ignoring side effects->pure looping\n");
385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
386 fprintf (dump_file
, " neihter\n");
387 *state
= IPA_NEITHER
;
392 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
393 into STATE and LOOPING better of the two variants.
394 Be sure to merge looping correctly. IPA_NEITHER functions
395 have looping 0 even if they don't have to return. */
398 better_state (enum pure_const_state_e
*state
, bool *looping
,
399 enum pure_const_state_e state2
, bool looping2
)
403 if (*state
== IPA_NEITHER
)
406 *looping
= MIN (*looping
, looping2
);
408 else if (state2
!= IPA_NEITHER
)
409 *looping
= MIN (*looping
, looping2
);
412 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
413 into STATE and LOOPING worse of the two variants. */
416 worse_state (enum pure_const_state_e
*state
, bool *looping
,
417 enum pure_const_state_e state2
, bool looping2
)
419 *state
= MAX (*state
, state2
);
420 *looping
= MAX (*looping
, looping2
);
423 /* Recognize special cases of builtins that are by themself not pure or const
424 but function using them is. */
426 special_builtlin_state (enum pure_const_state_e
*state
, bool *looping
,
429 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
430 switch (DECL_FUNCTION_CODE (callee
))
432 case BUILT_IN_RETURN
:
433 case BUILT_IN_UNREACHABLE
:
434 case BUILT_IN_ALLOCA
:
435 case BUILT_IN_STACK_SAVE
:
436 case BUILT_IN_STACK_RESTORE
:
437 case BUILT_IN_EH_POINTER
:
438 case BUILT_IN_EH_FILTER
:
439 case BUILT_IN_UNWIND_RESUME
:
440 case BUILT_IN_CXA_END_CLEANUP
:
441 case BUILT_IN_EH_COPY_VALUES
:
442 case BUILT_IN_FRAME_ADDRESS
:
444 case BUILT_IN_APPLY_ARGS
:
445 case BUILT_IN_ARGS_INFO
:
449 case BUILT_IN_PREFETCH
:
457 /* Check the parameters of a function call to CALL_EXPR to see if
458 there are any references in the parameters that are not allowed for
459 pure or const functions. Also check to see if this is either an
460 indirect call, a call outside the compilation unit, or has special
461 attributes that may also effect the purity. The CALL_EXPR node for
462 the entire call expression. */
465 check_call (funct_state local
, gimple call
, bool ipa
)
467 int flags
= gimple_call_flags (call
);
468 tree callee_t
= gimple_call_fndecl (call
);
469 bool possibly_throws
= stmt_could_throw_p (call
);
470 bool possibly_throws_externally
= (possibly_throws
471 && stmt_can_throw_external (call
));
476 for (i
= 0; i
< gimple_num_ops (call
); i
++)
477 if (gimple_op (call
, i
)
478 && tree_could_throw_p (gimple_op (call
, i
)))
480 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
483 fprintf (dump_file
, " operand can throw; looping\n");
484 local
->looping
= true;
486 if (possibly_throws_externally
)
489 fprintf (dump_file
, " operand can throw externally\n");
490 local
->can_throw
= true;
495 /* The const and pure flags are set by a variety of places in the
496 compiler (including here). If someone has already set the flags
497 for the callee, (such as for some of the builtins) we will use
498 them, otherwise we will compute our own information.
500 Const and pure functions have less clobber effects than other
501 functions so we process these first. Otherwise if it is a call
502 outside the compilation unit or an indirect call we punt. This
503 leaves local calls which will be processed by following the call
507 enum pure_const_state_e call_state
;
510 if (special_builtlin_state (&call_state
, &call_looping
, callee_t
))
512 worse_state (&local
->pure_const_state
, &local
->looping
,
513 call_state
, call_looping
);
516 /* When bad things happen to bad functions, they cannot be const
518 if (setjmp_call_p (callee_t
))
521 fprintf (dump_file
, " setjmp is not const/pure\n");
522 local
->looping
= true;
523 local
->pure_const_state
= IPA_NEITHER
;
526 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
527 switch (DECL_FUNCTION_CODE (callee_t
))
529 case BUILT_IN_LONGJMP
:
530 case BUILT_IN_NONLOCAL_GOTO
:
532 fprintf (dump_file
, " longjmp and nonlocal goto is not const/pure\n");
533 local
->pure_const_state
= IPA_NEITHER
;
534 local
->looping
= true;
541 /* When not in IPA mode, we can still handle self recursion. */
542 if (!ipa
&& callee_t
== current_function_decl
)
545 fprintf (dump_file
, " Recursive call can loop.\n");
546 local
->looping
= true;
548 /* Either calle is unknown or we are doing local analysis.
549 Look to see if there are any bits available for the callee (such as by
550 declaration or because it is builtin) and process solely on the basis of
554 enum pure_const_state_e call_state
;
556 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
559 fprintf (dump_file
, " can throw; looping\n");
560 local
->looping
= true;
562 if (possibly_throws_externally
)
566 fprintf (dump_file
, " can throw externally to lp %i\n",
567 lookup_stmt_eh_lp (call
));
569 fprintf (dump_file
, " callee:%s\n",
570 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t
)));
572 local
->can_throw
= true;
574 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
575 fprintf (dump_file
, " checking flags for call:");
576 state_from_flags (&call_state
, &call_looping
, flags
,
577 ((flags
& (ECF_NORETURN
| ECF_NOTHROW
))
578 == (ECF_NORETURN
| ECF_NOTHROW
))
579 || (!flag_exceptions
&& (flags
& ECF_NORETURN
)));
580 worse_state (&local
->pure_const_state
, &local
->looping
,
581 call_state
, call_looping
);
583 /* Direct functions calls are handled by IPA propagation. */
586 /* Wrapper around check_decl for loads in local more. */
589 check_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
592 check_decl ((funct_state
)data
, op
, false, false);
594 check_op ((funct_state
)data
, op
, false);
598 /* Wrapper around check_decl for stores in local more. */
601 check_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
604 check_decl ((funct_state
)data
, op
, true, false);
606 check_op ((funct_state
)data
, op
, true);
610 /* Wrapper around check_decl for loads in ipa mode. */
613 check_ipa_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
616 check_decl ((funct_state
)data
, op
, false, true);
618 check_op ((funct_state
)data
, op
, false);
622 /* Wrapper around check_decl for stores in ipa mode. */
625 check_ipa_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
628 check_decl ((funct_state
)data
, op
, true, true);
630 check_op ((funct_state
)data
, op
, true);
634 /* Look into pointer pointed to by GSIP and figure out what interesting side
637 check_stmt (gimple_stmt_iterator
*gsip
, funct_state local
, bool ipa
)
639 gimple stmt
= gsi_stmt (*gsip
);
642 if (is_gimple_debug (stmt
))
647 fprintf (dump_file
, " scanning: ");
648 print_gimple_stmt (dump_file
, stmt
, 0, 0);
651 /* Look for loads and stores. */
652 walk_stmt_load_store_ops (stmt
, local
,
653 ipa
? check_ipa_load
: check_load
,
654 ipa
? check_ipa_store
: check_store
);
656 if (gimple_code (stmt
) != GIMPLE_CALL
657 && stmt_could_throw_p (stmt
))
659 if (cfun
->can_throw_non_call_exceptions
)
662 fprintf (dump_file
, " can throw; looping");
663 local
->looping
= true;
665 if (stmt_can_throw_external (stmt
))
668 fprintf (dump_file
, " can throw externally");
669 local
->can_throw
= true;
672 switch (gimple_code (stmt
))
675 check_call (local
, stmt
, ipa
);
678 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
679 /* Target of long jump. */
682 fprintf (dump_file
, " nonlocal label is not const/pure");
683 local
->pure_const_state
= IPA_NEITHER
;
687 for (i
= 0; i
< gimple_asm_nclobbers (stmt
); i
++)
689 tree op
= gimple_asm_clobber_op (stmt
, i
);
690 if (strcmp (TREE_STRING_POINTER (TREE_VALUE (op
)), "memory") == 0)
693 fprintf (dump_file
, " memory asm clobber is not const/pure");
694 /* Abandon all hope, ye who enter here. */
695 local
->pure_const_state
= IPA_NEITHER
;
698 if (gimple_asm_volatile_p (stmt
))
701 fprintf (dump_file
, " volatile is not const/pure");
702 /* Abandon all hope, ye who enter here. */
703 local
->pure_const_state
= IPA_NEITHER
;
704 local
->looping
= true;
713 /* This is the main routine for finding the reference patterns for
714 global variables within a function FN. */
717 analyze_function (struct cgraph_node
*fn
, bool ipa
)
719 tree decl
= fn
->decl
;
720 tree old_decl
= current_function_decl
;
722 basic_block this_block
;
724 l
= XCNEW (struct funct_state_d
);
725 l
->pure_const_state
= IPA_CONST
;
726 l
->state_previously_known
= IPA_NEITHER
;
727 l
->looping_previously_known
= true;
729 l
->can_throw
= false;
733 fprintf (dump_file
, "\n\n local analysis of %s\n ",
734 cgraph_node_name (fn
));
737 push_cfun (DECL_STRUCT_FUNCTION (decl
));
738 current_function_decl
= decl
;
740 FOR_EACH_BB (this_block
)
742 gimple_stmt_iterator gsi
;
743 struct walk_stmt_info wi
;
745 memset (&wi
, 0, sizeof(wi
));
746 for (gsi
= gsi_start_bb (this_block
);
750 check_stmt (&gsi
, l
, ipa
);
751 if (l
->pure_const_state
== IPA_NEITHER
&& l
->looping
&& l
->can_throw
)
757 if (l
->pure_const_state
!= IPA_NEITHER
)
759 /* Const functions cannot have back edges (an
760 indication of possible infinite loop side
762 if (mark_dfs_back_edges ())
764 /* Preheaders are needed for SCEV to work.
765 Simple lateches and recorded exits improve chances that loop will
766 proved to be finite in testcases such as in loop-15.c and loop-24.c */
767 loop_optimizer_init (LOOPS_NORMAL
768 | LOOPS_HAVE_RECORDED_EXITS
);
769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
770 flow_loops_dump (dump_file
, NULL
, 0);
771 if (mark_irreducible_loops ())
774 fprintf (dump_file
, " has irreducible loops\n");
782 FOR_EACH_LOOP (li
, loop
, 0)
783 if (!finite_loop_p (loop
))
786 fprintf (dump_file
, " can not prove finiteness of loop %i\n", loop
->num
);
792 loop_optimizer_finalize ();
796 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
797 fprintf (dump_file
, " checking previously known:");
798 state_from_flags (&l
->state_previously_known
, &l
->looping_previously_known
,
799 flags_from_decl_or_type (fn
->decl
),
800 cgraph_node_cannot_return (fn
));
802 better_state (&l
->pure_const_state
, &l
->looping
,
803 l
->state_previously_known
,
804 l
->looping_previously_known
);
805 if (TREE_NOTHROW (decl
))
806 l
->can_throw
= false;
809 current_function_decl
= old_decl
;
813 fprintf (dump_file
, "Function is locally looping.\n");
815 fprintf (dump_file
, "Function is locally throwing.\n");
816 if (l
->pure_const_state
== IPA_CONST
)
817 fprintf (dump_file
, "Function is locally const.\n");
818 if (l
->pure_const_state
== IPA_PURE
)
819 fprintf (dump_file
, "Function is locally pure.\n");
824 /* Called when new function is inserted to callgraph late. */
826 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
828 if (cgraph_function_body_availability (node
) < AVAIL_OVERWRITABLE
)
830 /* There are some shared nodes, in particular the initializers on
831 static declarations. We do not need to scan them more than once
832 since all we would be interested in are the addressof
834 visited_nodes
= pointer_set_create ();
835 if (cgraph_function_body_availability (node
) > AVAIL_OVERWRITABLE
)
836 set_function_state (node
, analyze_function (node
, true));
837 pointer_set_destroy (visited_nodes
);
838 visited_nodes
= NULL
;
841 /* Called when new clone is inserted to callgraph late. */
844 duplicate_node_data (struct cgraph_node
*src
, struct cgraph_node
*dst
,
845 void *data ATTRIBUTE_UNUSED
)
847 if (has_function_state (src
))
849 funct_state l
= XNEW (struct funct_state_d
);
850 gcc_assert (!has_function_state (dst
));
851 memcpy (l
, get_function_state (src
), sizeof (*l
));
852 set_function_state (dst
, l
);
856 /* Called when new clone is inserted to callgraph late. */
859 remove_node_data (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
861 if (has_function_state (node
))
863 free (get_function_state (node
));
864 set_function_state (node
, NULL
);
870 register_hooks (void)
872 static bool init_p
= false;
879 node_removal_hook_holder
=
880 cgraph_add_node_removal_hook (&remove_node_data
, NULL
);
881 node_duplication_hook_holder
=
882 cgraph_add_node_duplication_hook (&duplicate_node_data
, NULL
);
883 function_insertion_hook_holder
=
884 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
888 /* Analyze each function in the cgraph to see if it is locally PURE or
892 generate_summary (void)
894 struct cgraph_node
*node
;
898 /* There are some shared nodes, in particular the initializers on
899 static declarations. We do not need to scan them more than once
900 since all we would be interested in are the addressof
902 visited_nodes
= pointer_set_create ();
904 /* Process all of the functions.
906 We process AVAIL_OVERWRITABLE functions. We can not use the results
907 by default, but the info can be used at LTO with -fwhole-program or
908 when function got clonned and the clone is AVAILABLE. */
910 for (node
= cgraph_nodes
; node
; node
= node
->next
)
911 if (cgraph_function_body_availability (node
) >= AVAIL_OVERWRITABLE
)
912 set_function_state (node
, analyze_function (node
, true));
914 pointer_set_destroy (visited_nodes
);
915 visited_nodes
= NULL
;
919 /* Serialize the ipa info for lto. */
922 pure_const_write_summary (cgraph_node_set set
,
923 varpool_node_set vset ATTRIBUTE_UNUSED
)
925 struct cgraph_node
*node
;
926 struct lto_simple_output_block
*ob
927 = lto_create_simple_output_block (LTO_section_ipa_pure_const
);
928 unsigned int count
= 0;
929 cgraph_node_set_iterator csi
;
931 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
933 node
= csi_node (csi
);
934 if (node
->analyzed
&& has_function_state (node
))
938 lto_output_uleb128_stream (ob
->main_stream
, count
);
940 /* Process all of the functions. */
941 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
943 node
= csi_node (csi
);
944 if (node
->analyzed
&& has_function_state (node
))
949 lto_cgraph_encoder_t encoder
;
951 fs
= get_function_state (node
);
953 encoder
= ob
->decl_state
->cgraph_node_encoder
;
954 node_ref
= lto_cgraph_encoder_encode (encoder
, node
);
955 lto_output_uleb128_stream (ob
->main_stream
, node_ref
);
957 /* Note that flags will need to be read in the opposite
958 order as we are pushing the bitflags into FLAGS. */
959 bp
= bitpack_create (ob
->main_stream
);
960 bp_pack_value (&bp
, fs
->pure_const_state
, 2);
961 bp_pack_value (&bp
, fs
->state_previously_known
, 2);
962 bp_pack_value (&bp
, fs
->looping_previously_known
, 1);
963 bp_pack_value (&bp
, fs
->looping
, 1);
964 bp_pack_value (&bp
, fs
->can_throw
, 1);
965 lto_output_bitpack (&bp
);
969 lto_destroy_simple_output_block (ob
);
973 /* Deserialize the ipa info for lto. */
976 pure_const_read_summary (void)
978 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
979 struct lto_file_decl_data
*file_data
;
983 while ((file_data
= file_data_vec
[j
++]))
987 struct lto_input_block
*ib
988 = lto_create_simple_input_block (file_data
,
989 LTO_section_ipa_pure_const
,
994 unsigned int count
= lto_input_uleb128 (ib
);
996 for (i
= 0; i
< count
; i
++)
999 struct cgraph_node
*node
;
1000 struct bitpack_d bp
;
1002 lto_cgraph_encoder_t encoder
;
1004 fs
= XCNEW (struct funct_state_d
);
1005 index
= lto_input_uleb128 (ib
);
1006 encoder
= file_data
->cgraph_node_encoder
;
1007 node
= lto_cgraph_encoder_deref (encoder
, index
);
1008 set_function_state (node
, fs
);
1010 /* Note that the flags must be read in the opposite
1011 order in which they were written (the bitflags were
1012 pushed into FLAGS). */
1013 bp
= lto_input_bitpack (ib
);
1014 fs
->pure_const_state
1015 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1016 fs
->state_previously_known
1017 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1018 fs
->looping_previously_known
= bp_unpack_value (&bp
, 1);
1019 fs
->looping
= bp_unpack_value (&bp
, 1);
1020 fs
->can_throw
= bp_unpack_value (&bp
, 1);
1023 int flags
= flags_from_decl_or_type (node
->decl
);
1024 fprintf (dump_file
, "Read info for %s/%i ",
1025 cgraph_node_name (node
),
1027 if (flags
& ECF_CONST
)
1028 fprintf (dump_file
, " const");
1029 if (flags
& ECF_PURE
)
1030 fprintf (dump_file
, " pure");
1031 if (flags
& ECF_NOTHROW
)
1032 fprintf (dump_file
, " nothrow");
1033 fprintf (dump_file
, "\n pure const state: %s\n",
1034 pure_const_names
[fs
->pure_const_state
]);
1035 fprintf (dump_file
, " previously known state: %s\n",
1036 pure_const_names
[fs
->looping_previously_known
]);
1038 fprintf (dump_file
," function is locally looping\n");
1039 if (fs
->looping_previously_known
)
1040 fprintf (dump_file
," function is previously known looping\n");
1042 fprintf (dump_file
," function is locally throwing\n");
1046 lto_destroy_simple_input_block (file_data
,
1047 LTO_section_ipa_pure_const
,
1055 ignore_edge (struct cgraph_edge
*e
)
1057 return (!e
->can_throw_external
);
1060 /* Return true if NODE is self recursive function. */
1063 self_recursive_p (struct cgraph_node
*node
)
1065 struct cgraph_edge
*e
;
1066 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1067 if (e
->callee
== node
)
1072 /* Produce transitive closure over the callgraph and compute pure/const
1076 propagate_pure_const (void)
1078 struct cgraph_node
*node
;
1079 struct cgraph_node
*w
;
1080 struct cgraph_node
**order
=
1081 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1084 struct ipa_dfs_info
* w_info
;
1086 order_pos
= ipa_utils_reduced_inorder (order
, true, false, NULL
);
1089 dump_cgraph (dump_file
);
1090 ipa_utils_print_order(dump_file
, "reduced", order
, order_pos
);
1093 /* Propagate the local information thru the call graph to produce
1094 the global information. All the nodes within a cycle will have
1095 the same info so we collapse cycles first. Then we can do the
1096 propagation in one pass from the leaves to the roots. */
1097 for (i
= 0; i
< order_pos
; i
++ )
1099 enum pure_const_state_e pure_const_state
= IPA_CONST
;
1100 bool looping
= false;
1104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1105 fprintf (dump_file
, "Starting cycle\n");
1107 /* Find the worst state for any node in the cycle. */
1109 while (w
&& pure_const_state
!= IPA_NEITHER
)
1111 struct cgraph_edge
*e
;
1112 struct cgraph_edge
*ie
;
1114 struct ipa_ref
*ref
;
1116 funct_state w_l
= get_function_state (w
);
1117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1118 fprintf (dump_file
, " Visiting %s/%i state:%s looping %i\n",
1119 cgraph_node_name (w
),
1121 pure_const_names
[w_l
->pure_const_state
],
1124 /* First merge in function body properties. */
1125 worse_state (&pure_const_state
, &looping
,
1126 w_l
->pure_const_state
, w_l
->looping
);
1127 if (pure_const_state
== IPA_NEITHER
)
1130 /* For overwritable nodes we can not assume anything. */
1131 if (cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1133 worse_state (&pure_const_state
, &looping
,
1134 w_l
->state_previously_known
,
1135 w_l
->looping_previously_known
);
1136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1139 " Overwritable. state %s looping %i\n",
1140 pure_const_names
[w_l
->state_previously_known
],
1141 w_l
->looping_previously_known
);
1148 /* We consider recursive cycles as possibly infinite.
1149 This might be relaxed since infinite recursion leads to stack
1154 /* Now walk the edges and merge in callee properties. */
1155 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1157 struct cgraph_node
*y
= e
->callee
;
1158 enum pure_const_state_e edge_state
= IPA_CONST
;
1159 bool edge_looping
= false;
1161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1165 cgraph_node_name (e
->callee
),
1168 if (cgraph_function_body_availability (y
) > AVAIL_OVERWRITABLE
)
1170 funct_state y_l
= get_function_state (y
);
1171 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1174 " state:%s looping:%i\n",
1175 pure_const_names
[y_l
->pure_const_state
],
1178 if (y_l
->pure_const_state
> IPA_PURE
1179 && cgraph_edge_cannot_lead_to_return (e
))
1181 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1183 " Ignoring side effects"
1184 " -> pure, looping\n");
1185 edge_state
= IPA_PURE
;
1186 edge_looping
= true;
1190 edge_state
= y_l
->pure_const_state
;
1191 edge_looping
= y_l
->looping
;
1194 else if (special_builtlin_state (&edge_state
, &edge_looping
,
1198 state_from_flags (&edge_state
, &edge_looping
,
1199 flags_from_decl_or_type (y
->decl
),
1200 cgraph_edge_cannot_lead_to_return (e
));
1202 /* Merge the results with what we already know. */
1203 better_state (&edge_state
, &edge_looping
,
1204 w_l
->state_previously_known
,
1205 w_l
->looping_previously_known
);
1206 worse_state (&pure_const_state
, &looping
,
1207 edge_state
, edge_looping
);
1208 if (pure_const_state
== IPA_NEITHER
)
1211 if (pure_const_state
== IPA_NEITHER
)
1214 /* Now process the indirect call. */
1215 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1217 enum pure_const_state_e edge_state
= IPA_CONST
;
1218 bool edge_looping
= false;
1220 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1221 fprintf (dump_file
, " Indirect call");
1222 state_from_flags (&edge_state
, &edge_looping
,
1223 ie
->indirect_info
->ecf_flags
,
1224 cgraph_edge_cannot_lead_to_return (ie
));
1225 /* Merge the results with what we already know. */
1226 better_state (&edge_state
, &edge_looping
,
1227 w_l
->state_previously_known
,
1228 w_l
->looping_previously_known
);
1229 worse_state (&pure_const_state
, &looping
,
1230 edge_state
, edge_looping
);
1231 if (pure_const_state
== IPA_NEITHER
)
1234 if (pure_const_state
== IPA_NEITHER
)
1237 /* And finally all loads and stores. */
1238 for (i
= 0; ipa_ref_list_reference_iterate (&node
->ref_list
, i
, ref
); i
++)
1240 enum pure_const_state_e ref_state
= IPA_CONST
;
1241 bool ref_looping
= false;
1245 /* readonly reads are safe. */
1246 if (TREE_READONLY (ipa_ref_varpool_node (ref
)->decl
))
1248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1249 fprintf (dump_file
, " nonreadonly global var read\n");
1250 ref_state
= IPA_PURE
;
1253 if (ipa_ref_cannot_lead_to_return (ref
))
1255 ref_state
= IPA_NEITHER
;
1256 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1257 fprintf (dump_file
, " global var write\n");
1262 better_state (&ref_state
, &ref_looping
,
1263 w_l
->state_previously_known
,
1264 w_l
->looping_previously_known
);
1265 worse_state (&pure_const_state
, &looping
,
1266 ref_state
, ref_looping
);
1267 if (pure_const_state
== IPA_NEITHER
)
1270 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1271 w
= w_info
->next_cycle
;
1273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1274 fprintf (dump_file
, "Result %s looping %i\n",
1275 pure_const_names
[pure_const_state
],
1278 /* Copy back the region's pure_const_state which is shared by
1279 all nodes in the region. */
1283 funct_state w_l
= get_function_state (w
);
1284 enum pure_const_state_e this_state
= pure_const_state
;
1285 bool this_looping
= looping
;
1287 if (w_l
->state_previously_known
!= IPA_NEITHER
1288 && this_state
> w_l
->state_previously_known
)
1290 this_state
= w_l
->state_previously_known
;
1291 this_looping
|= w_l
->looping_previously_known
;
1293 if (!this_looping
&& self_recursive_p (w
))
1294 this_looping
= true;
1295 if (!w_l
->looping_previously_known
)
1296 this_looping
= false;
1298 /* All nodes within a cycle share the same info. */
1299 w_l
->pure_const_state
= this_state
;
1300 w_l
->looping
= this_looping
;
1305 if (!TREE_READONLY (w
->decl
))
1307 warn_function_const (w
->decl
, !this_looping
);
1309 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1310 this_looping
? "looping " : "",
1311 cgraph_node_name (w
));
1313 cgraph_set_readonly_flag (w
, true);
1314 cgraph_set_looping_const_or_pure_flag (w
, this_looping
);
1318 if (!DECL_PURE_P (w
->decl
))
1320 warn_function_pure (w
->decl
, !this_looping
);
1322 fprintf (dump_file
, "Function found to be %spure: %s\n",
1323 this_looping
? "looping " : "",
1324 cgraph_node_name (w
));
1326 cgraph_set_pure_flag (w
, true);
1327 cgraph_set_looping_const_or_pure_flag (w
, this_looping
);
1333 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1334 w
= w_info
->next_cycle
;
1339 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1341 /* Get rid of the aux information. */
1344 w_info
= (struct ipa_dfs_info
*) node
->aux
;
1353 /* Produce transitive closure over the callgraph and compute nothrow
1357 propagate_nothrow (void)
1359 struct cgraph_node
*node
;
1360 struct cgraph_node
*w
;
1361 struct cgraph_node
**order
=
1362 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1365 struct ipa_dfs_info
* w_info
;
1367 order_pos
= ipa_utils_reduced_inorder (order
, true, false, ignore_edge
);
1370 dump_cgraph (dump_file
);
1371 ipa_utils_print_order(dump_file
, "reduced for nothrow", order
, order_pos
);
1374 /* Propagate the local information thru the call graph to produce
1375 the global information. All the nodes within a cycle will have
1376 the same info so we collapse cycles first. Then we can do the
1377 propagation in one pass from the leaves to the roots. */
1378 for (i
= 0; i
< order_pos
; i
++ )
1380 bool can_throw
= false;
1383 /* Find the worst state for any node in the cycle. */
1387 struct cgraph_edge
*e
, *ie
;
1388 funct_state w_l
= get_function_state (w
);
1391 || cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1397 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1399 struct cgraph_node
*y
= e
->callee
;
1401 if (cgraph_function_body_availability (y
) > AVAIL_OVERWRITABLE
)
1403 funct_state y_l
= get_function_state (y
);
1407 if (y_l
->can_throw
&& !TREE_NOTHROW (w
->decl
)
1408 && e
->can_throw_external
)
1411 else if (e
->can_throw_external
&& !TREE_NOTHROW (y
->decl
))
1414 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1415 if (ie
->can_throw_external
)
1417 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1418 w
= w_info
->next_cycle
;
1421 /* Copy back the region's pure_const_state which is shared by
1422 all nodes in the region. */
1426 funct_state w_l
= get_function_state (w
);
1427 if (!can_throw
&& !TREE_NOTHROW (w
->decl
))
1429 struct cgraph_edge
*e
;
1430 cgraph_set_nothrow_flag (w
, true);
1431 for (e
= w
->callers
; e
; e
= e
->next_caller
)
1432 e
->can_throw_external
= false;
1434 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1435 cgraph_node_name (w
));
1437 else if (can_throw
&& !TREE_NOTHROW (w
->decl
))
1438 w_l
->can_throw
= true;
1439 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1440 w
= w_info
->next_cycle
;
1445 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1447 /* Get rid of the aux information. */
1450 w_info
= (struct ipa_dfs_info
*) node
->aux
;
1460 /* Produce the global information by preforming a transitive closure
1461 on the local information that was produced by generate_summary. */
1466 struct cgraph_node
*node
;
1468 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1469 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
1470 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
1472 /* Nothrow makes more function to not lead to return and improve
1474 propagate_nothrow ();
1475 propagate_pure_const ();
1478 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1479 if (has_function_state (node
))
1480 free (get_function_state (node
));
1481 VEC_free (funct_state
, heap
, funct_state_vec
);
1487 gate_pure_const (void)
1489 return (flag_ipa_pure_const
1490 /* Don't bother doing anything if the program has errors. */
1494 struct ipa_opt_pass_d pass_ipa_pure_const
=
1498 "pure-const", /* name */
1499 gate_pure_const
, /* gate */
1500 propagate
, /* execute */
1503 0, /* static_pass_number */
1504 TV_IPA_PURE_CONST
, /* tv_id */
1505 0, /* properties_required */
1506 0, /* properties_provided */
1507 0, /* properties_destroyed */
1508 0, /* todo_flags_start */
1509 0 /* todo_flags_finish */
1511 generate_summary
, /* generate_summary */
1512 pure_const_write_summary
, /* write_summary */
1513 pure_const_read_summary
, /* read_summary */
1514 NULL
, /* write_optimization_summary */
1515 NULL
, /* read_optimization_summary */
1516 NULL
, /* stmt_fixup */
1518 NULL
, /* function_transform */
1519 NULL
/* variable_transform */
1522 /* Return true if function should be skipped for local pure const analysis. */
1525 skip_function_for_local_pure_const (struct cgraph_node
*node
)
1527 /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1528 we must not promote functions that are called by already processed functions. */
1530 if (function_called_by_processed_nodes_p ())
1533 fprintf (dump_file
, "Function called in recursive cycle; ignoring\n");
1536 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
1539 fprintf (dump_file
, "Function is not available or overwrittable; not analyzing.\n");
1545 /* Simple local pass for pure const discovery reusing the analysis from
1546 ipa_pure_const. This pass is effective when executed together with
1547 other optimization passes in early optimization pass queue. */
1550 local_pure_const (void)
1552 bool changed
= false;
1555 struct cgraph_node
*node
;
1557 node
= cgraph_node (current_function_decl
);
1558 skip
= skip_function_for_local_pure_const (node
);
1559 if (!warn_suggest_attribute_const
1560 && !warn_suggest_attribute_pure
1564 /* First do NORETURN discovery. */
1565 if (!skip
&& !TREE_THIS_VOLATILE (current_function_decl
)
1566 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 0)
1568 warn_function_noreturn (cfun
->decl
);
1570 fprintf (dump_file
, "Function found to be noreturn: %s\n",
1571 lang_hooks
.decl_printable_name (current_function_decl
, 2));
1573 /* Update declaration and reduce profile to executed once. */
1574 TREE_THIS_VOLATILE (current_function_decl
) = 1;
1575 if (node
->frequency
> NODE_FREQUENCY_EXECUTED_ONCE
)
1576 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
1580 l
= analyze_function (node
, false);
1582 switch (l
->pure_const_state
)
1585 if (!TREE_READONLY (current_function_decl
))
1587 warn_function_const (current_function_decl
, !l
->looping
);
1590 cgraph_set_readonly_flag (node
, true);
1591 cgraph_set_looping_const_or_pure_flag (node
, l
->looping
);
1595 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1596 l
->looping
? "looping " : "",
1597 lang_hooks
.decl_printable_name (current_function_decl
,
1600 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1605 cgraph_set_looping_const_or_pure_flag (node
, false);
1609 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1610 lang_hooks
.decl_printable_name (current_function_decl
,
1616 if (!DECL_PURE_P (current_function_decl
))
1620 cgraph_set_pure_flag (node
, true);
1621 cgraph_set_looping_const_or_pure_flag (node
, l
->looping
);
1624 warn_function_pure (current_function_decl
, !l
->looping
);
1626 fprintf (dump_file
, "Function found to be %spure: %s\n",
1627 l
->looping
? "looping " : "",
1628 lang_hooks
.decl_printable_name (current_function_decl
,
1631 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1636 cgraph_set_looping_const_or_pure_flag (node
, false);
1640 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1641 lang_hooks
.decl_printable_name (current_function_decl
,
1649 if (!l
->can_throw
&& !TREE_NOTHROW (current_function_decl
))
1651 struct cgraph_edge
*e
;
1653 cgraph_set_nothrow_flag (node
, true);
1654 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1655 e
->can_throw_external
= false;
1658 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1659 lang_hooks
.decl_printable_name (current_function_decl
,
1665 return execute_fixup_cfg ();
1670 struct gimple_opt_pass pass_local_pure_const
=
1674 "local-pure-const", /* name */
1675 gate_pure_const
, /* gate */
1676 local_pure_const
, /* execute */
1679 0, /* static_pass_number */
1680 TV_IPA_PURE_CONST
, /* tv_id */
1681 0, /* properties_required */
1682 0, /* properties_provided */
1683 0, /* properties_destroyed */
1684 0, /* todo_flags_start */
1685 0 /* todo_flags_finish */