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 /* State used when we know nothing about function. */
99 static struct funct_state_d varying_state
100 = { IPA_NEITHER
, IPA_NEITHER
, true, true, true };
103 typedef struct funct_state_d
* funct_state
;
105 /* The storage of the funct_state is abstracted because there is the
106 possibility that it may be desirable to move this to the cgraph
109 /* Array, indexed by cgraph node uid, of function states. */
111 DEF_VEC_P (funct_state
);
112 DEF_VEC_ALLOC_P (funct_state
, heap
);
113 static VEC (funct_state
, heap
) *funct_state_vec
;
115 /* Holders of ipa cgraph hooks: */
116 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
117 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
118 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
120 /* Try to guess if function body will always be visible to compiler
121 when compiling the call and whether compiler will be able
122 to propagate the information by itself. */
125 function_always_visible_to_compiler_p (tree decl
)
127 return (!TREE_PUBLIC (decl
) || DECL_DECLARED_INLINE_P (decl
));
130 /* Emit suggestion about attribute ATTRIB_NAME for DECL. KNOWN_FINITE
131 is true if the function is known to be finite. The diagnostic is
132 controlled by OPTION. WARNED_ABOUT is a pointer_set unique for
133 OPTION, this function may initialize it and it is always returned
136 static struct pointer_set_t
*
137 suggest_attribute (int option
, tree decl
, bool known_finite
,
138 struct pointer_set_t
*warned_about
,
139 const char * attrib_name
)
141 if (!option_enabled (option
))
143 if (TREE_THIS_VOLATILE (decl
)
144 || (known_finite
&& function_always_visible_to_compiler_p (decl
)))
148 warned_about
= pointer_set_create ();
149 if (pointer_set_contains (warned_about
, decl
))
151 pointer_set_insert (warned_about
, decl
);
152 warning_at (DECL_SOURCE_LOCATION (decl
),
155 ? _("function might be candidate for attribute %<%s%>")
156 : _("function might be candidate for attribute %<%s%>"
157 " if it is known to return normally"), attrib_name
);
161 /* Emit suggestion about __attribute_((pure)) for DECL. KNOWN_FINITE
162 is true if the function is known to be finite. */
165 warn_function_pure (tree decl
, bool known_finite
)
167 static struct pointer_set_t
*warned_about
;
170 = suggest_attribute (OPT_Wsuggest_attribute_pure
, decl
,
171 known_finite
, warned_about
, "pure");
174 /* Emit suggestion about __attribute_((const)) for DECL. KNOWN_FINITE
175 is true if the function is known to be finite. */
178 warn_function_const (tree decl
, bool known_finite
)
180 static struct pointer_set_t
*warned_about
;
182 = suggest_attribute (OPT_Wsuggest_attribute_const
, decl
,
183 known_finite
, warned_about
, "const");
187 warn_function_noreturn (tree decl
)
189 static struct pointer_set_t
*warned_about
;
190 if (!lang_hooks
.missing_noreturn_ok_p (decl
))
192 = suggest_attribute (OPT_Wsuggest_attribute_noreturn
, decl
,
193 true, warned_about
, "noreturn");
195 /* Init the function state. */
200 free (funct_state_vec
);
204 /* Return true if we have a function state for NODE. */
207 has_function_state (struct cgraph_node
*node
)
210 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
212 return VEC_index (funct_state
, funct_state_vec
, node
->uid
) != NULL
;
215 /* Return the function state from NODE. */
217 static inline funct_state
218 get_function_state (struct cgraph_node
*node
)
221 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
222 || !VEC_index (funct_state
, funct_state_vec
, node
->uid
))
223 /* We might want to put correct previously_known state into varying. */
224 return &varying_state
;
225 return VEC_index (funct_state
, funct_state_vec
, node
->uid
);
228 /* Set the function state S for NODE. */
231 set_function_state (struct cgraph_node
*node
, funct_state s
)
234 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
235 VEC_safe_grow_cleared (funct_state
, heap
, funct_state_vec
, node
->uid
+ 1);
236 VEC_replace (funct_state
, funct_state_vec
, node
->uid
, s
);
239 /* Check to see if the use (or definition when CHECKING_WRITE is true)
240 variable T is legal in a function that is either pure or const. */
243 check_decl (funct_state local
,
244 tree t
, bool checking_write
, bool ipa
)
246 /* Do not want to do anything with volatile except mark any
247 function that uses one to be not const or pure. */
248 if (TREE_THIS_VOLATILE (t
))
250 local
->pure_const_state
= IPA_NEITHER
;
252 fprintf (dump_file
, " Volatile operand is not const/pure");
256 /* Do not care about a local automatic that is not static. */
257 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
260 /* If the variable has the "used" attribute, treat it as if it had a
261 been touched by the devil. */
262 if (DECL_PRESERVE_P (t
))
264 local
->pure_const_state
= IPA_NEITHER
;
266 fprintf (dump_file
, " Used static/global variable is not const/pure\n");
270 /* In IPA mode we are not interested in checking actual loads and stores;
271 they will be processed at propagation time using ipa_ref. */
275 /* Since we have dealt with the locals and params cases above, if we
276 are CHECKING_WRITE, this cannot be a pure or constant
280 local
->pure_const_state
= IPA_NEITHER
;
282 fprintf (dump_file
, " static/global memory write is not const/pure\n");
286 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
288 /* Readonly reads are safe. */
289 if (TREE_READONLY (t
) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t
)))
290 return; /* Read of a constant, do not change the function state. */
294 fprintf (dump_file
, " global memory read is not const\n");
295 /* Just a regular read. */
296 if (local
->pure_const_state
== IPA_CONST
)
297 local
->pure_const_state
= IPA_PURE
;
302 /* Compilation level statics can be read if they are readonly
304 if (TREE_READONLY (t
))
308 fprintf (dump_file
, " static memory read is not const\n");
309 /* Just a regular read. */
310 if (local
->pure_const_state
== IPA_CONST
)
311 local
->pure_const_state
= IPA_PURE
;
316 /* Check to see if the use (or definition when CHECKING_WRITE is true)
317 variable T is legal in a function that is either pure or const. */
320 check_op (funct_state local
, tree t
, bool checking_write
)
322 t
= get_base_address (t
);
323 if (t
&& TREE_THIS_VOLATILE (t
))
325 local
->pure_const_state
= IPA_NEITHER
;
327 fprintf (dump_file
, " Volatile indirect ref is not const/pure\n");
331 && (INDIRECT_REF_P (t
) || TREE_CODE (t
) == MEM_REF
)
332 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
333 && !ptr_deref_may_alias_global_p (TREE_OPERAND (t
, 0)))
336 fprintf (dump_file
, " Indirect ref to local memory is OK\n");
339 else if (checking_write
)
341 local
->pure_const_state
= IPA_NEITHER
;
343 fprintf (dump_file
, " Indirect ref write is not const/pure\n");
349 fprintf (dump_file
, " Indirect ref read is not const\n");
350 if (local
->pure_const_state
== IPA_CONST
)
351 local
->pure_const_state
= IPA_PURE
;
355 /* compute state based on ECF FLAGS and store to STATE and LOOPING. */
358 state_from_flags (enum pure_const_state_e
*state
, bool *looping
,
359 int flags
, bool cannot_lead_to_return
)
362 if (flags
& ECF_LOOPING_CONST_OR_PURE
)
365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
366 fprintf (dump_file
, " looping");
368 if (flags
& ECF_CONST
)
371 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, " const\n");
374 else if (flags
& ECF_PURE
)
377 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
378 fprintf (dump_file
, " pure\n");
380 else if (cannot_lead_to_return
)
384 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
385 fprintf (dump_file
, " ignoring side effects->pure looping\n");
389 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
390 fprintf (dump_file
, " neihter\n");
391 *state
= IPA_NEITHER
;
396 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
397 into STATE and LOOPING better of the two variants.
398 Be sure to merge looping correctly. IPA_NEITHER functions
399 have looping 0 even if they don't have to return. */
402 better_state (enum pure_const_state_e
*state
, bool *looping
,
403 enum pure_const_state_e state2
, bool looping2
)
407 if (*state
== IPA_NEITHER
)
410 *looping
= MIN (*looping
, looping2
);
412 else if (state2
!= IPA_NEITHER
)
413 *looping
= MIN (*looping
, looping2
);
416 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
417 into STATE and LOOPING worse of the two variants. */
420 worse_state (enum pure_const_state_e
*state
, bool *looping
,
421 enum pure_const_state_e state2
, bool looping2
)
423 *state
= MAX (*state
, state2
);
424 *looping
= MAX (*looping
, looping2
);
427 /* Recognize special cases of builtins that are by themself not pure or const
428 but function using them is. */
430 special_builtlin_state (enum pure_const_state_e
*state
, bool *looping
,
433 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
434 switch (DECL_FUNCTION_CODE (callee
))
436 case BUILT_IN_RETURN
:
437 case BUILT_IN_UNREACHABLE
:
438 case BUILT_IN_ALLOCA
:
439 case BUILT_IN_STACK_SAVE
:
440 case BUILT_IN_STACK_RESTORE
:
441 case BUILT_IN_EH_POINTER
:
442 case BUILT_IN_EH_FILTER
:
443 case BUILT_IN_UNWIND_RESUME
:
444 case BUILT_IN_CXA_END_CLEANUP
:
445 case BUILT_IN_EH_COPY_VALUES
:
446 case BUILT_IN_FRAME_ADDRESS
:
448 case BUILT_IN_APPLY_ARGS
:
452 case BUILT_IN_PREFETCH
:
460 /* Check the parameters of a function call to CALL_EXPR to see if
461 there are any references in the parameters that are not allowed for
462 pure or const functions. Also check to see if this is either an
463 indirect call, a call outside the compilation unit, or has special
464 attributes that may also effect the purity. The CALL_EXPR node for
465 the entire call expression. */
468 check_call (funct_state local
, gimple call
, bool ipa
)
470 int flags
= gimple_call_flags (call
);
471 tree callee_t
= gimple_call_fndecl (call
);
472 bool possibly_throws
= stmt_could_throw_p (call
);
473 bool possibly_throws_externally
= (possibly_throws
474 && stmt_can_throw_external (call
));
479 for (i
= 0; i
< gimple_num_ops (call
); i
++)
480 if (gimple_op (call
, i
)
481 && tree_could_throw_p (gimple_op (call
, i
)))
483 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
486 fprintf (dump_file
, " operand can throw; looping\n");
487 local
->looping
= true;
489 if (possibly_throws_externally
)
492 fprintf (dump_file
, " operand can throw externally\n");
493 local
->can_throw
= true;
498 /* The const and pure flags are set by a variety of places in the
499 compiler (including here). If someone has already set the flags
500 for the callee, (such as for some of the builtins) we will use
501 them, otherwise we will compute our own information.
503 Const and pure functions have less clobber effects than other
504 functions so we process these first. Otherwise if it is a call
505 outside the compilation unit or an indirect call we punt. This
506 leaves local calls which will be processed by following the call
510 enum pure_const_state_e call_state
;
513 if (special_builtlin_state (&call_state
, &call_looping
, callee_t
))
515 worse_state (&local
->pure_const_state
, &local
->looping
,
516 call_state
, call_looping
);
519 /* When bad things happen to bad functions, they cannot be const
521 if (setjmp_call_p (callee_t
))
524 fprintf (dump_file
, " setjmp is not const/pure\n");
525 local
->looping
= true;
526 local
->pure_const_state
= IPA_NEITHER
;
529 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
530 switch (DECL_FUNCTION_CODE (callee_t
))
532 case BUILT_IN_LONGJMP
:
533 case BUILT_IN_NONLOCAL_GOTO
:
535 fprintf (dump_file
, " longjmp and nonlocal goto is not const/pure\n");
536 local
->pure_const_state
= IPA_NEITHER
;
537 local
->looping
= true;
544 /* When not in IPA mode, we can still handle self recursion. */
545 if (!ipa
&& callee_t
== current_function_decl
)
548 fprintf (dump_file
, " Recursive call can loop.\n");
549 local
->looping
= true;
551 /* Either calle is unknown or we are doing local analysis.
552 Look to see if there are any bits available for the callee (such as by
553 declaration or because it is builtin) and process solely on the basis of
557 enum pure_const_state_e call_state
;
559 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
562 fprintf (dump_file
, " can throw; looping\n");
563 local
->looping
= true;
565 if (possibly_throws_externally
)
569 fprintf (dump_file
, " can throw externally to lp %i\n",
570 lookup_stmt_eh_lp (call
));
572 fprintf (dump_file
, " callee:%s\n",
573 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t
)));
575 local
->can_throw
= true;
577 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
578 fprintf (dump_file
, " checking flags for call:");
579 state_from_flags (&call_state
, &call_looping
, flags
,
580 ((flags
& (ECF_NORETURN
| ECF_NOTHROW
))
581 == (ECF_NORETURN
| ECF_NOTHROW
))
582 || (!flag_exceptions
&& (flags
& ECF_NORETURN
)));
583 worse_state (&local
->pure_const_state
, &local
->looping
,
584 call_state
, call_looping
);
586 /* Direct functions calls are handled by IPA propagation. */
589 /* Wrapper around check_decl for loads in local more. */
592 check_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
595 check_decl ((funct_state
)data
, op
, false, false);
597 check_op ((funct_state
)data
, op
, false);
601 /* Wrapper around check_decl for stores in local more. */
604 check_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
607 check_decl ((funct_state
)data
, op
, true, false);
609 check_op ((funct_state
)data
, op
, true);
613 /* Wrapper around check_decl for loads in ipa mode. */
616 check_ipa_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
619 check_decl ((funct_state
)data
, op
, false, true);
621 check_op ((funct_state
)data
, op
, false);
625 /* Wrapper around check_decl for stores in ipa mode. */
628 check_ipa_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
631 check_decl ((funct_state
)data
, op
, true, true);
633 check_op ((funct_state
)data
, op
, true);
637 /* Look into pointer pointed to by GSIP and figure out what interesting side
640 check_stmt (gimple_stmt_iterator
*gsip
, funct_state local
, bool ipa
)
642 gimple stmt
= gsi_stmt (*gsip
);
645 if (is_gimple_debug (stmt
))
650 fprintf (dump_file
, " scanning: ");
651 print_gimple_stmt (dump_file
, stmt
, 0, 0);
654 /* Look for loads and stores. */
655 walk_stmt_load_store_ops (stmt
, local
,
656 ipa
? check_ipa_load
: check_load
,
657 ipa
? check_ipa_store
: check_store
);
659 if (gimple_code (stmt
) != GIMPLE_CALL
660 && stmt_could_throw_p (stmt
))
662 if (cfun
->can_throw_non_call_exceptions
)
665 fprintf (dump_file
, " can throw; looping");
666 local
->looping
= true;
668 if (stmt_can_throw_external (stmt
))
671 fprintf (dump_file
, " can throw externally");
672 local
->can_throw
= true;
675 switch (gimple_code (stmt
))
678 check_call (local
, stmt
, ipa
);
681 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
682 /* Target of long jump. */
685 fprintf (dump_file
, " nonlocal label is not const/pure");
686 local
->pure_const_state
= IPA_NEITHER
;
690 for (i
= 0; i
< gimple_asm_nclobbers (stmt
); i
++)
692 tree op
= gimple_asm_clobber_op (stmt
, i
);
693 if (strcmp (TREE_STRING_POINTER (TREE_VALUE (op
)), "memory") == 0)
696 fprintf (dump_file
, " memory asm clobber is not const/pure");
697 /* Abandon all hope, ye who enter here. */
698 local
->pure_const_state
= IPA_NEITHER
;
701 if (gimple_asm_volatile_p (stmt
))
704 fprintf (dump_file
, " volatile is not const/pure");
705 /* Abandon all hope, ye who enter here. */
706 local
->pure_const_state
= IPA_NEITHER
;
707 local
->looping
= true;
716 /* This is the main routine for finding the reference patterns for
717 global variables within a function FN. */
720 analyze_function (struct cgraph_node
*fn
, bool ipa
)
722 tree decl
= fn
->decl
;
725 basic_block this_block
;
727 l
= XCNEW (struct funct_state_d
);
728 l
->state_previously_known
= IPA_NEITHER
;
729 l
->looping_previously_known
= true;
731 l
->can_throw
= false;
732 if (DECL_IS_IFUNC (decl
))
734 l
->pure_const_state
= IPA_NEITHER
;
738 l
->pure_const_state
= IPA_CONST
;
742 fprintf (dump_file
, "\n\n local analysis of %s\n ",
743 cgraph_node_name (fn
));
746 old_decl
= current_function_decl
;
748 push_cfun (DECL_STRUCT_FUNCTION (decl
));
749 current_function_decl
= decl
;
751 FOR_EACH_BB (this_block
)
753 gimple_stmt_iterator gsi
;
754 struct walk_stmt_info wi
;
756 memset (&wi
, 0, sizeof(wi
));
757 for (gsi
= gsi_start_bb (this_block
);
761 check_stmt (&gsi
, l
, ipa
);
762 if (l
->pure_const_state
== IPA_NEITHER
&& l
->looping
&& l
->can_throw
)
768 if (l
->pure_const_state
!= IPA_NEITHER
)
770 /* Const functions cannot have back edges (an
771 indication of possible infinite loop side
773 if (mark_dfs_back_edges ())
775 /* Preheaders are needed for SCEV to work.
776 Simple lateches and recorded exits improve chances that loop will
777 proved to be finite in testcases such as in loop-15.c and loop-24.c */
778 loop_optimizer_init (LOOPS_NORMAL
779 | LOOPS_HAVE_RECORDED_EXITS
);
780 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
781 flow_loops_dump (dump_file
, NULL
, 0);
782 if (mark_irreducible_loops ())
785 fprintf (dump_file
, " has irreducible loops\n");
793 FOR_EACH_LOOP (li
, loop
, 0)
794 if (!finite_loop_p (loop
))
797 fprintf (dump_file
, " can not prove finiteness of loop %i\n", loop
->num
);
803 loop_optimizer_finalize ();
807 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
808 fprintf (dump_file
, " checking previously known:");
809 state_from_flags (&l
->state_previously_known
, &l
->looping_previously_known
,
810 flags_from_decl_or_type (fn
->decl
),
811 cgraph_node_cannot_return (fn
));
813 better_state (&l
->pure_const_state
, &l
->looping
,
814 l
->state_previously_known
,
815 l
->looping_previously_known
);
816 if (TREE_NOTHROW (decl
))
817 l
->can_throw
= false;
820 current_function_decl
= old_decl
;
826 fprintf (dump_file
, "Function is locally looping.\n");
828 fprintf (dump_file
, "Function is locally throwing.\n");
829 if (l
->pure_const_state
== IPA_CONST
)
830 fprintf (dump_file
, "Function is locally const.\n");
831 if (l
->pure_const_state
== IPA_PURE
)
832 fprintf (dump_file
, "Function is locally pure.\n");
837 /* Called when new function is inserted to callgraph late. */
839 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
841 if (cgraph_function_body_availability (node
) < AVAIL_OVERWRITABLE
)
843 /* There are some shared nodes, in particular the initializers on
844 static declarations. We do not need to scan them more than once
845 since all we would be interested in are the addressof
847 visited_nodes
= pointer_set_create ();
848 if (cgraph_function_body_availability (node
) > AVAIL_OVERWRITABLE
)
849 set_function_state (node
, analyze_function (node
, true));
850 pointer_set_destroy (visited_nodes
);
851 visited_nodes
= NULL
;
854 /* Called when new clone is inserted to callgraph late. */
857 duplicate_node_data (struct cgraph_node
*src
, struct cgraph_node
*dst
,
858 void *data ATTRIBUTE_UNUSED
)
860 if (has_function_state (src
))
862 funct_state l
= XNEW (struct funct_state_d
);
863 gcc_assert (!has_function_state (dst
));
864 memcpy (l
, get_function_state (src
), sizeof (*l
));
865 set_function_state (dst
, l
);
869 /* Called when new clone is inserted to callgraph late. */
872 remove_node_data (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
874 if (has_function_state (node
))
876 funct_state l
= get_function_state (node
);
877 if (l
!= &varying_state
)
879 set_function_state (node
, NULL
);
885 register_hooks (void)
887 static bool init_p
= false;
894 node_removal_hook_holder
=
895 cgraph_add_node_removal_hook (&remove_node_data
, NULL
);
896 node_duplication_hook_holder
=
897 cgraph_add_node_duplication_hook (&duplicate_node_data
, NULL
);
898 function_insertion_hook_holder
=
899 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
903 /* Analyze each function in the cgraph to see if it is locally PURE or
907 generate_summary (void)
909 struct cgraph_node
*node
;
913 /* There are some shared nodes, in particular the initializers on
914 static declarations. We do not need to scan them more than once
915 since all we would be interested in are the addressof
917 visited_nodes
= pointer_set_create ();
919 /* Process all of the functions.
921 We process AVAIL_OVERWRITABLE functions. We can not use the results
922 by default, but the info can be used at LTO with -fwhole-program or
923 when function got clonned and the clone is AVAILABLE. */
925 for (node
= cgraph_nodes
; node
; node
= node
->next
)
926 if (cgraph_function_body_availability (node
) >= AVAIL_OVERWRITABLE
)
927 set_function_state (node
, analyze_function (node
, true));
929 pointer_set_destroy (visited_nodes
);
930 visited_nodes
= NULL
;
934 /* Serialize the ipa info for lto. */
937 pure_const_write_summary (cgraph_node_set set
,
938 varpool_node_set vset ATTRIBUTE_UNUSED
)
940 struct cgraph_node
*node
;
941 struct lto_simple_output_block
*ob
942 = lto_create_simple_output_block (LTO_section_ipa_pure_const
);
943 unsigned int count
= 0;
944 cgraph_node_set_iterator csi
;
946 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
948 node
= csi_node (csi
);
949 if (node
->analyzed
&& has_function_state (node
))
953 lto_output_uleb128_stream (ob
->main_stream
, count
);
955 /* Process all of the functions. */
956 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
958 node
= csi_node (csi
);
959 if (node
->analyzed
&& has_function_state (node
))
964 lto_cgraph_encoder_t encoder
;
966 fs
= get_function_state (node
);
968 encoder
= ob
->decl_state
->cgraph_node_encoder
;
969 node_ref
= lto_cgraph_encoder_encode (encoder
, node
);
970 lto_output_uleb128_stream (ob
->main_stream
, node_ref
);
972 /* Note that flags will need to be read in the opposite
973 order as we are pushing the bitflags into FLAGS. */
974 bp
= bitpack_create (ob
->main_stream
);
975 bp_pack_value (&bp
, fs
->pure_const_state
, 2);
976 bp_pack_value (&bp
, fs
->state_previously_known
, 2);
977 bp_pack_value (&bp
, fs
->looping_previously_known
, 1);
978 bp_pack_value (&bp
, fs
->looping
, 1);
979 bp_pack_value (&bp
, fs
->can_throw
, 1);
980 lto_output_bitpack (&bp
);
984 lto_destroy_simple_output_block (ob
);
988 /* Deserialize the ipa info for lto. */
991 pure_const_read_summary (void)
993 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
994 struct lto_file_decl_data
*file_data
;
998 while ((file_data
= file_data_vec
[j
++]))
1002 struct lto_input_block
*ib
1003 = lto_create_simple_input_block (file_data
,
1004 LTO_section_ipa_pure_const
,
1009 unsigned int count
= lto_input_uleb128 (ib
);
1011 for (i
= 0; i
< count
; i
++)
1014 struct cgraph_node
*node
;
1015 struct bitpack_d bp
;
1017 lto_cgraph_encoder_t encoder
;
1019 fs
= XCNEW (struct funct_state_d
);
1020 index
= lto_input_uleb128 (ib
);
1021 encoder
= file_data
->cgraph_node_encoder
;
1022 node
= lto_cgraph_encoder_deref (encoder
, index
);
1023 set_function_state (node
, fs
);
1025 /* Note that the flags must be read in the opposite
1026 order in which they were written (the bitflags were
1027 pushed into FLAGS). */
1028 bp
= lto_input_bitpack (ib
);
1029 fs
->pure_const_state
1030 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1031 fs
->state_previously_known
1032 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1033 fs
->looping_previously_known
= bp_unpack_value (&bp
, 1);
1034 fs
->looping
= bp_unpack_value (&bp
, 1);
1035 fs
->can_throw
= bp_unpack_value (&bp
, 1);
1038 int flags
= flags_from_decl_or_type (node
->decl
);
1039 fprintf (dump_file
, "Read info for %s/%i ",
1040 cgraph_node_name (node
),
1042 if (flags
& ECF_CONST
)
1043 fprintf (dump_file
, " const");
1044 if (flags
& ECF_PURE
)
1045 fprintf (dump_file
, " pure");
1046 if (flags
& ECF_NOTHROW
)
1047 fprintf (dump_file
, " nothrow");
1048 fprintf (dump_file
, "\n pure const state: %s\n",
1049 pure_const_names
[fs
->pure_const_state
]);
1050 fprintf (dump_file
, " previously known state: %s\n",
1051 pure_const_names
[fs
->looping_previously_known
]);
1053 fprintf (dump_file
," function is locally looping\n");
1054 if (fs
->looping_previously_known
)
1055 fprintf (dump_file
," function is previously known looping\n");
1057 fprintf (dump_file
," function is locally throwing\n");
1061 lto_destroy_simple_input_block (file_data
,
1062 LTO_section_ipa_pure_const
,
1070 ignore_edge (struct cgraph_edge
*e
)
1072 return (!e
->can_throw_external
);
1075 /* Return true if NODE is self recursive function. */
1078 self_recursive_p (struct cgraph_node
*node
)
1080 struct cgraph_edge
*e
;
1081 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1082 if (e
->callee
== node
)
1087 /* Produce transitive closure over the callgraph and compute pure/const
1091 propagate_pure_const (void)
1093 struct cgraph_node
*node
;
1094 struct cgraph_node
*w
;
1095 struct cgraph_node
**order
=
1096 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1099 struct ipa_dfs_info
* w_info
;
1101 order_pos
= ipa_utils_reduced_inorder (order
, true, false, NULL
);
1104 dump_cgraph (dump_file
);
1105 ipa_utils_print_order(dump_file
, "reduced", order
, order_pos
);
1108 /* Propagate the local information thru the call graph to produce
1109 the global information. All the nodes within a cycle will have
1110 the same info so we collapse cycles first. Then we can do the
1111 propagation in one pass from the leaves to the roots. */
1112 for (i
= 0; i
< order_pos
; i
++ )
1114 enum pure_const_state_e pure_const_state
= IPA_CONST
;
1115 bool looping
= false;
1119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1120 fprintf (dump_file
, "Starting cycle\n");
1122 /* Find the worst state for any node in the cycle. */
1124 while (w
&& pure_const_state
!= IPA_NEITHER
)
1126 struct cgraph_edge
*e
;
1127 struct cgraph_edge
*ie
;
1129 struct ipa_ref
*ref
;
1131 funct_state w_l
= get_function_state (w
);
1132 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1133 fprintf (dump_file
, " Visiting %s/%i state:%s looping %i\n",
1134 cgraph_node_name (w
),
1136 pure_const_names
[w_l
->pure_const_state
],
1139 /* First merge in function body properties. */
1140 worse_state (&pure_const_state
, &looping
,
1141 w_l
->pure_const_state
, w_l
->looping
);
1142 if (pure_const_state
== IPA_NEITHER
)
1145 /* For overwritable nodes we can not assume anything. */
1146 if (cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1148 worse_state (&pure_const_state
, &looping
,
1149 w_l
->state_previously_known
,
1150 w_l
->looping_previously_known
);
1151 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1154 " Overwritable. state %s looping %i\n",
1155 pure_const_names
[w_l
->state_previously_known
],
1156 w_l
->looping_previously_known
);
1163 /* We consider recursive cycles as possibly infinite.
1164 This might be relaxed since infinite recursion leads to stack
1169 /* Now walk the edges and merge in callee properties. */
1170 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1172 struct cgraph_node
*y
= e
->callee
;
1173 enum pure_const_state_e edge_state
= IPA_CONST
;
1174 bool edge_looping
= false;
1176 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1180 cgraph_node_name (e
->callee
),
1183 if (cgraph_function_body_availability (y
) > AVAIL_OVERWRITABLE
)
1185 funct_state y_l
= get_function_state (y
);
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1189 " state:%s looping:%i\n",
1190 pure_const_names
[y_l
->pure_const_state
],
1193 if (y_l
->pure_const_state
> IPA_PURE
1194 && cgraph_edge_cannot_lead_to_return (e
))
1196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1198 " Ignoring side effects"
1199 " -> pure, looping\n");
1200 edge_state
= IPA_PURE
;
1201 edge_looping
= true;
1205 edge_state
= y_l
->pure_const_state
;
1206 edge_looping
= y_l
->looping
;
1209 else if (special_builtlin_state (&edge_state
, &edge_looping
,
1213 state_from_flags (&edge_state
, &edge_looping
,
1214 flags_from_decl_or_type (y
->decl
),
1215 cgraph_edge_cannot_lead_to_return (e
));
1217 /* Merge the results with what we already know. */
1218 better_state (&edge_state
, &edge_looping
,
1219 w_l
->state_previously_known
,
1220 w_l
->looping_previously_known
);
1221 worse_state (&pure_const_state
, &looping
,
1222 edge_state
, edge_looping
);
1223 if (pure_const_state
== IPA_NEITHER
)
1226 if (pure_const_state
== IPA_NEITHER
)
1229 /* Now process the indirect call. */
1230 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1232 enum pure_const_state_e edge_state
= IPA_CONST
;
1233 bool edge_looping
= false;
1235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1236 fprintf (dump_file
, " Indirect call");
1237 state_from_flags (&edge_state
, &edge_looping
,
1238 ie
->indirect_info
->ecf_flags
,
1239 cgraph_edge_cannot_lead_to_return (ie
));
1240 /* Merge the results with what we already know. */
1241 better_state (&edge_state
, &edge_looping
,
1242 w_l
->state_previously_known
,
1243 w_l
->looping_previously_known
);
1244 worse_state (&pure_const_state
, &looping
,
1245 edge_state
, edge_looping
);
1246 if (pure_const_state
== IPA_NEITHER
)
1249 if (pure_const_state
== IPA_NEITHER
)
1252 /* And finally all loads and stores. */
1253 for (i
= 0; ipa_ref_list_reference_iterate (&node
->ref_list
, i
, ref
); i
++)
1255 enum pure_const_state_e ref_state
= IPA_CONST
;
1256 bool ref_looping
= false;
1260 /* readonly reads are safe. */
1261 if (TREE_READONLY (ipa_ref_varpool_node (ref
)->decl
))
1263 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1264 fprintf (dump_file
, " nonreadonly global var read\n");
1265 ref_state
= IPA_PURE
;
1268 if (ipa_ref_cannot_lead_to_return (ref
))
1270 ref_state
= IPA_NEITHER
;
1271 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1272 fprintf (dump_file
, " global var write\n");
1277 better_state (&ref_state
, &ref_looping
,
1278 w_l
->state_previously_known
,
1279 w_l
->looping_previously_known
);
1280 worse_state (&pure_const_state
, &looping
,
1281 ref_state
, ref_looping
);
1282 if (pure_const_state
== IPA_NEITHER
)
1285 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1286 w
= w_info
->next_cycle
;
1288 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1289 fprintf (dump_file
, "Result %s looping %i\n",
1290 pure_const_names
[pure_const_state
],
1293 /* Copy back the region's pure_const_state which is shared by
1294 all nodes in the region. */
1298 funct_state w_l
= get_function_state (w
);
1299 enum pure_const_state_e this_state
= pure_const_state
;
1300 bool this_looping
= looping
;
1302 if (w_l
->state_previously_known
!= IPA_NEITHER
1303 && this_state
> w_l
->state_previously_known
)
1305 this_state
= w_l
->state_previously_known
;
1306 this_looping
|= w_l
->looping_previously_known
;
1308 if (!this_looping
&& self_recursive_p (w
))
1309 this_looping
= true;
1310 if (!w_l
->looping_previously_known
)
1311 this_looping
= false;
1313 /* All nodes within a cycle share the same info. */
1314 w_l
->pure_const_state
= this_state
;
1315 w_l
->looping
= this_looping
;
1320 if (!TREE_READONLY (w
->decl
))
1322 warn_function_const (w
->decl
, !this_looping
);
1324 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1325 this_looping
? "looping " : "",
1326 cgraph_node_name (w
));
1328 cgraph_set_readonly_flag (w
, true);
1329 cgraph_set_looping_const_or_pure_flag (w
, this_looping
);
1333 if (!DECL_PURE_P (w
->decl
))
1335 warn_function_pure (w
->decl
, !this_looping
);
1337 fprintf (dump_file
, "Function found to be %spure: %s\n",
1338 this_looping
? "looping " : "",
1339 cgraph_node_name (w
));
1341 cgraph_set_pure_flag (w
, true);
1342 cgraph_set_looping_const_or_pure_flag (w
, this_looping
);
1348 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1349 w
= w_info
->next_cycle
;
1354 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1356 /* Get rid of the aux information. */
1359 w_info
= (struct ipa_dfs_info
*) node
->aux
;
1368 /* Produce transitive closure over the callgraph and compute nothrow
1372 propagate_nothrow (void)
1374 struct cgraph_node
*node
;
1375 struct cgraph_node
*w
;
1376 struct cgraph_node
**order
=
1377 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1380 struct ipa_dfs_info
* w_info
;
1382 order_pos
= ipa_utils_reduced_inorder (order
, true, false, ignore_edge
);
1385 dump_cgraph (dump_file
);
1386 ipa_utils_print_order(dump_file
, "reduced for nothrow", order
, order_pos
);
1389 /* Propagate the local information thru the call graph to produce
1390 the global information. All the nodes within a cycle will have
1391 the same info so we collapse cycles first. Then we can do the
1392 propagation in one pass from the leaves to the roots. */
1393 for (i
= 0; i
< order_pos
; i
++ )
1395 bool can_throw
= false;
1398 /* Find the worst state for any node in the cycle. */
1402 struct cgraph_edge
*e
, *ie
;
1403 funct_state w_l
= get_function_state (w
);
1406 || cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1412 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1414 struct cgraph_node
*y
= e
->callee
;
1416 if (cgraph_function_body_availability (y
) > AVAIL_OVERWRITABLE
)
1418 funct_state y_l
= get_function_state (y
);
1422 if (y_l
->can_throw
&& !TREE_NOTHROW (w
->decl
)
1423 && e
->can_throw_external
)
1426 else if (e
->can_throw_external
&& !TREE_NOTHROW (y
->decl
))
1429 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1430 if (ie
->can_throw_external
)
1432 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1433 w
= w_info
->next_cycle
;
1436 /* Copy back the region's pure_const_state which is shared by
1437 all nodes in the region. */
1441 funct_state w_l
= get_function_state (w
);
1442 if (!can_throw
&& !TREE_NOTHROW (w
->decl
))
1444 struct cgraph_edge
*e
;
1445 cgraph_set_nothrow_flag (w
, true);
1446 for (e
= w
->callers
; e
; e
= e
->next_caller
)
1447 e
->can_throw_external
= false;
1449 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1450 cgraph_node_name (w
));
1452 else if (can_throw
&& !TREE_NOTHROW (w
->decl
))
1453 w_l
->can_throw
= true;
1454 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1455 w
= w_info
->next_cycle
;
1460 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1462 /* Get rid of the aux information. */
1465 w_info
= (struct ipa_dfs_info
*) node
->aux
;
1475 /* Produce the global information by preforming a transitive closure
1476 on the local information that was produced by generate_summary. */
1481 struct cgraph_node
*node
;
1483 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1484 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
1485 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
1487 /* Nothrow makes more function to not lead to return and improve
1489 propagate_nothrow ();
1490 propagate_pure_const ();
1493 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1494 if (has_function_state (node
))
1495 free (get_function_state (node
));
1496 VEC_free (funct_state
, heap
, funct_state_vec
);
1502 gate_pure_const (void)
1504 return (flag_ipa_pure_const
1505 /* Don't bother doing anything if the program has errors. */
1509 struct ipa_opt_pass_d pass_ipa_pure_const
=
1513 "pure-const", /* name */
1514 gate_pure_const
, /* gate */
1515 propagate
, /* execute */
1518 0, /* static_pass_number */
1519 TV_IPA_PURE_CONST
, /* tv_id */
1520 0, /* properties_required */
1521 0, /* properties_provided */
1522 0, /* properties_destroyed */
1523 0, /* todo_flags_start */
1524 0 /* todo_flags_finish */
1526 generate_summary
, /* generate_summary */
1527 pure_const_write_summary
, /* write_summary */
1528 pure_const_read_summary
, /* read_summary */
1529 NULL
, /* write_optimization_summary */
1530 NULL
, /* read_optimization_summary */
1531 NULL
, /* stmt_fixup */
1533 NULL
, /* function_transform */
1534 NULL
/* variable_transform */
1537 /* Return true if function should be skipped for local pure const analysis. */
1540 skip_function_for_local_pure_const (struct cgraph_node
*node
)
1542 /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1543 we must not promote functions that are called by already processed functions. */
1545 if (function_called_by_processed_nodes_p ())
1548 fprintf (dump_file
, "Function called in recursive cycle; ignoring\n");
1551 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
1554 fprintf (dump_file
, "Function is not available or overwrittable; not analyzing.\n");
1560 /* Simple local pass for pure const discovery reusing the analysis from
1561 ipa_pure_const. This pass is effective when executed together with
1562 other optimization passes in early optimization pass queue. */
1565 local_pure_const (void)
1567 bool changed
= false;
1570 struct cgraph_node
*node
;
1572 node
= cgraph_node (current_function_decl
);
1573 skip
= skip_function_for_local_pure_const (node
);
1574 if (!warn_suggest_attribute_const
1575 && !warn_suggest_attribute_pure
1579 /* First do NORETURN discovery. */
1580 if (!skip
&& !TREE_THIS_VOLATILE (current_function_decl
)
1581 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 0)
1583 warn_function_noreturn (cfun
->decl
);
1585 fprintf (dump_file
, "Function found to be noreturn: %s\n",
1586 lang_hooks
.decl_printable_name (current_function_decl
, 2));
1588 /* Update declaration and reduce profile to executed once. */
1589 TREE_THIS_VOLATILE (current_function_decl
) = 1;
1590 if (node
->frequency
> NODE_FREQUENCY_EXECUTED_ONCE
)
1591 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
1595 l
= analyze_function (node
, false);
1597 switch (l
->pure_const_state
)
1600 if (!TREE_READONLY (current_function_decl
))
1602 warn_function_const (current_function_decl
, !l
->looping
);
1605 cgraph_set_readonly_flag (node
, true);
1606 cgraph_set_looping_const_or_pure_flag (node
, l
->looping
);
1610 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1611 l
->looping
? "looping " : "",
1612 lang_hooks
.decl_printable_name (current_function_decl
,
1615 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1620 cgraph_set_looping_const_or_pure_flag (node
, false);
1624 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1625 lang_hooks
.decl_printable_name (current_function_decl
,
1631 if (!DECL_PURE_P (current_function_decl
))
1635 cgraph_set_pure_flag (node
, true);
1636 cgraph_set_looping_const_or_pure_flag (node
, l
->looping
);
1639 warn_function_pure (current_function_decl
, !l
->looping
);
1641 fprintf (dump_file
, "Function found to be %spure: %s\n",
1642 l
->looping
? "looping " : "",
1643 lang_hooks
.decl_printable_name (current_function_decl
,
1646 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1651 cgraph_set_looping_const_or_pure_flag (node
, false);
1655 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1656 lang_hooks
.decl_printable_name (current_function_decl
,
1664 if (!l
->can_throw
&& !TREE_NOTHROW (current_function_decl
))
1666 struct cgraph_edge
*e
;
1668 cgraph_set_nothrow_flag (node
, true);
1669 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1670 e
->can_throw_external
= false;
1673 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1674 lang_hooks
.decl_printable_name (current_function_decl
,
1680 return execute_fixup_cfg ();
1685 struct gimple_opt_pass pass_local_pure_const
=
1689 "local-pure-const", /* name */
1690 gate_pure_const
, /* gate */
1691 local_pure_const
, /* execute */
1694 0, /* static_pass_number */
1695 TV_IPA_PURE_CONST
, /* tv_id */
1696 0, /* properties_required */
1697 0, /* properties_provided */
1698 0, /* properties_destroyed */
1699 0, /* todo_flags_start */
1700 0 /* todo_flags_finish */