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"
50 #include "diagnostic.h"
51 #include "gimple-pretty-print.h"
52 #include "langhooks.h"
54 #include "lto-streamer.h"
55 #include "data-streamer.h"
56 #include "tree-streamer.h"
58 #include "tree-scalar-evolution.h"
62 static struct pointer_set_t
*visited_nodes
;
64 /* Lattice values for const and pure functions. Everything starts out
65 being const, then may drop to pure and then neither depending on
67 enum pure_const_state_e
74 const char *pure_const_names
[3] = {"const", "pure", "neither"};
76 /* Holder for the const_state. There is one of these per function
81 enum pure_const_state_e pure_const_state
;
82 /* What user set here; we can be always sure about this. */
83 enum pure_const_state_e state_previously_known
;
84 bool looping_previously_known
;
86 /* True if the function could possibly infinite loop. There are a
87 lot of ways that this could be determined. We are pretty
88 conservative here. While it is possible to cse pure and const
89 calls, it is not legal to have dce get rid of the call if there
90 is a possibility that the call could infinite loop since this is
91 a behavioral change. */
97 /* State used when we know nothing about function. */
98 static struct funct_state_d varying_state
99 = { IPA_NEITHER
, IPA_NEITHER
, true, true, true };
102 typedef struct funct_state_d
* funct_state
;
104 /* The storage of the funct_state is abstracted because there is the
105 possibility that it may be desirable to move this to the cgraph
108 /* Array, indexed by cgraph node uid, of function states. */
110 DEF_VEC_P (funct_state
);
111 DEF_VEC_ALLOC_P (funct_state
, heap
);
112 static VEC (funct_state
, heap
) *funct_state_vec
;
114 /* Holders of ipa cgraph hooks: */
115 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
116 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
117 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
119 /* Try to guess if function body will always be visible to compiler
120 when compiling the call and whether compiler will be able
121 to propagate the information by itself. */
124 function_always_visible_to_compiler_p (tree decl
)
126 return (!TREE_PUBLIC (decl
) || DECL_DECLARED_INLINE_P (decl
));
129 /* Emit suggestion about attribute ATTRIB_NAME for DECL. KNOWN_FINITE
130 is true if the function is known to be finite. The diagnostic is
131 controlled by OPTION. WARNED_ABOUT is a pointer_set unique for
132 OPTION, this function may initialize it and it is always returned
135 static struct pointer_set_t
*
136 suggest_attribute (int option
, tree decl
, bool known_finite
,
137 struct pointer_set_t
*warned_about
,
138 const char * attrib_name
)
140 if (!option_enabled (option
, &global_options
))
142 if (TREE_THIS_VOLATILE (decl
)
143 || (known_finite
&& function_always_visible_to_compiler_p (decl
)))
147 warned_about
= pointer_set_create ();
148 if (pointer_set_contains (warned_about
, decl
))
150 pointer_set_insert (warned_about
, decl
);
151 warning_at (DECL_SOURCE_LOCATION (decl
),
154 ? _("function might be candidate for attribute %<%s%>")
155 : _("function might be candidate for attribute %<%s%>"
156 " if it is known to return normally"), attrib_name
);
160 /* Emit suggestion about __attribute_((pure)) for DECL. KNOWN_FINITE
161 is true if the function is known to be finite. */
164 warn_function_pure (tree decl
, bool known_finite
)
166 static struct pointer_set_t
*warned_about
;
169 = suggest_attribute (OPT_Wsuggest_attribute_pure
, decl
,
170 known_finite
, warned_about
, "pure");
173 /* Emit suggestion about __attribute_((const)) for DECL. KNOWN_FINITE
174 is true if the function is known to be finite. */
177 warn_function_const (tree decl
, bool known_finite
)
179 static struct pointer_set_t
*warned_about
;
181 = suggest_attribute (OPT_Wsuggest_attribute_const
, decl
,
182 known_finite
, warned_about
, "const");
186 warn_function_noreturn (tree decl
)
188 static struct pointer_set_t
*warned_about
;
189 if (!lang_hooks
.missing_noreturn_ok_p (decl
)
190 && targetm
.warn_func_return (decl
))
192 = suggest_attribute (OPT_Wsuggest_attribute_noreturn
, decl
,
193 true, warned_about
, "noreturn");
196 /* Init the function state. */
201 free (funct_state_vec
);
205 /* Return true if we have a function state for NODE. */
208 has_function_state (struct cgraph_node
*node
)
211 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
213 return VEC_index (funct_state
, funct_state_vec
, node
->uid
) != NULL
;
216 /* Return the function state from NODE. */
218 static inline funct_state
219 get_function_state (struct cgraph_node
*node
)
222 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
223 || !VEC_index (funct_state
, funct_state_vec
, node
->uid
))
224 /* We might want to put correct previously_known state into varying. */
225 return &varying_state
;
226 return VEC_index (funct_state
, funct_state_vec
, node
->uid
);
229 /* Set the function state S for NODE. */
232 set_function_state (struct cgraph_node
*node
, funct_state s
)
235 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
236 VEC_safe_grow_cleared (funct_state
, heap
, funct_state_vec
, node
->uid
+ 1);
237 VEC_replace (funct_state
, funct_state_vec
, node
->uid
, s
);
240 /* Check to see if the use (or definition when CHECKING_WRITE is true)
241 variable T is legal in a function that is either pure or const. */
244 check_decl (funct_state local
,
245 tree t
, bool checking_write
, bool ipa
)
247 /* Do not want to do anything with volatile except mark any
248 function that uses one to be not const or pure. */
249 if (TREE_THIS_VOLATILE (t
))
251 local
->pure_const_state
= IPA_NEITHER
;
253 fprintf (dump_file
, " Volatile operand is not const/pure");
257 /* Do not care about a local automatic that is not static. */
258 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
261 /* If the variable has the "used" attribute, treat it as if it had a
262 been touched by the devil. */
263 if (DECL_PRESERVE_P (t
))
265 local
->pure_const_state
= IPA_NEITHER
;
267 fprintf (dump_file
, " Used static/global variable is not const/pure\n");
271 /* In IPA mode we are not interested in checking actual loads and stores;
272 they will be processed at propagation time using ipa_ref. */
276 /* Since we have dealt with the locals and params cases above, if we
277 are CHECKING_WRITE, this cannot be a pure or constant
281 local
->pure_const_state
= IPA_NEITHER
;
283 fprintf (dump_file
, " static/global memory write is not const/pure\n");
287 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
289 /* Readonly reads are safe. */
290 if (TREE_READONLY (t
) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t
)))
291 return; /* Read of a constant, do not change the function state. */
295 fprintf (dump_file
, " global memory read is not const\n");
296 /* Just a regular read. */
297 if (local
->pure_const_state
== IPA_CONST
)
298 local
->pure_const_state
= IPA_PURE
;
303 /* Compilation level statics can be read if they are readonly
305 if (TREE_READONLY (t
))
309 fprintf (dump_file
, " static memory read is not const\n");
310 /* Just a regular read. */
311 if (local
->pure_const_state
== IPA_CONST
)
312 local
->pure_const_state
= IPA_PURE
;
317 /* Check to see if the use (or definition when CHECKING_WRITE is true)
318 variable T is legal in a function that is either pure or const. */
321 check_op (funct_state local
, tree t
, bool checking_write
)
323 t
= get_base_address (t
);
324 if (t
&& TREE_THIS_VOLATILE (t
))
326 local
->pure_const_state
= IPA_NEITHER
;
328 fprintf (dump_file
, " Volatile indirect ref is not const/pure\n");
332 && (INDIRECT_REF_P (t
) || TREE_CODE (t
) == MEM_REF
)
333 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
334 && !ptr_deref_may_alias_global_p (TREE_OPERAND (t
, 0)))
337 fprintf (dump_file
, " Indirect ref to local memory is OK\n");
340 else if (checking_write
)
342 local
->pure_const_state
= IPA_NEITHER
;
344 fprintf (dump_file
, " Indirect ref write is not const/pure\n");
350 fprintf (dump_file
, " Indirect ref read is not const\n");
351 if (local
->pure_const_state
== IPA_CONST
)
352 local
->pure_const_state
= IPA_PURE
;
356 /* compute state based on ECF FLAGS and store to STATE and LOOPING. */
359 state_from_flags (enum pure_const_state_e
*state
, bool *looping
,
360 int flags
, bool cannot_lead_to_return
)
363 if (flags
& ECF_LOOPING_CONST_OR_PURE
)
366 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
367 fprintf (dump_file
, " looping");
369 if (flags
& ECF_CONST
)
372 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
373 fprintf (dump_file
, " const\n");
375 else if (flags
& ECF_PURE
)
378 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
379 fprintf (dump_file
, " pure\n");
381 else if (cannot_lead_to_return
)
385 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
386 fprintf (dump_file
, " ignoring side effects->pure looping\n");
390 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
391 fprintf (dump_file
, " neither\n");
392 *state
= IPA_NEITHER
;
397 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
398 into STATE and LOOPING better of the two variants.
399 Be sure to merge looping correctly. IPA_NEITHER functions
400 have looping 0 even if they don't have to return. */
403 better_state (enum pure_const_state_e
*state
, bool *looping
,
404 enum pure_const_state_e state2
, bool looping2
)
408 if (*state
== IPA_NEITHER
)
411 *looping
= MIN (*looping
, looping2
);
413 else if (state2
!= IPA_NEITHER
)
414 *looping
= MIN (*looping
, looping2
);
417 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
418 into STATE and LOOPING worse of the two variants. */
421 worse_state (enum pure_const_state_e
*state
, bool *looping
,
422 enum pure_const_state_e state2
, bool looping2
)
424 *state
= MAX (*state
, state2
);
425 *looping
= MAX (*looping
, looping2
);
428 /* Recognize special cases of builtins that are by themselves not pure or const
429 but function using them is. */
431 special_builtin_state (enum pure_const_state_e
*state
, bool *looping
,
434 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
435 switch (DECL_FUNCTION_CODE (callee
))
437 case BUILT_IN_RETURN
:
438 case BUILT_IN_UNREACHABLE
:
439 case BUILT_IN_ALLOCA
:
440 case BUILT_IN_ALLOCA_WITH_ALIGN
:
441 case BUILT_IN_STACK_SAVE
:
442 case BUILT_IN_STACK_RESTORE
:
443 case BUILT_IN_EH_POINTER
:
444 case BUILT_IN_EH_FILTER
:
445 case BUILT_IN_UNWIND_RESUME
:
446 case BUILT_IN_CXA_END_CLEANUP
:
447 case BUILT_IN_EH_COPY_VALUES
:
448 case BUILT_IN_FRAME_ADDRESS
:
450 case BUILT_IN_APPLY_ARGS
:
454 case BUILT_IN_PREFETCH
:
462 /* Check the parameters of a function call to CALL_EXPR to see if
463 there are any references in the parameters that are not allowed for
464 pure or const functions. Also check to see if this is either an
465 indirect call, a call outside the compilation unit, or has special
466 attributes that may also effect the purity. The CALL_EXPR node for
467 the entire call expression. */
470 check_call (funct_state local
, gimple call
, bool ipa
)
472 int flags
= gimple_call_flags (call
);
473 tree callee_t
= gimple_call_fndecl (call
);
474 bool possibly_throws
= stmt_could_throw_p (call
);
475 bool possibly_throws_externally
= (possibly_throws
476 && stmt_can_throw_external (call
));
481 for (i
= 0; i
< gimple_num_ops (call
); i
++)
482 if (gimple_op (call
, i
)
483 && tree_could_throw_p (gimple_op (call
, i
)))
485 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
488 fprintf (dump_file
, " operand can throw; looping\n");
489 local
->looping
= true;
491 if (possibly_throws_externally
)
494 fprintf (dump_file
, " operand can throw externally\n");
495 local
->can_throw
= true;
500 /* The const and pure flags are set by a variety of places in the
501 compiler (including here). If someone has already set the flags
502 for the callee, (such as for some of the builtins) we will use
503 them, otherwise we will compute our own information.
505 Const and pure functions have less clobber effects than other
506 functions so we process these first. Otherwise if it is a call
507 outside the compilation unit or an indirect call we punt. This
508 leaves local calls which will be processed by following the call
512 enum pure_const_state_e call_state
;
515 if (special_builtin_state (&call_state
, &call_looping
, callee_t
))
517 worse_state (&local
->pure_const_state
, &local
->looping
,
518 call_state
, call_looping
);
521 /* When bad things happen to bad functions, they cannot be const
523 if (setjmp_call_p (callee_t
))
526 fprintf (dump_file
, " setjmp is not const/pure\n");
527 local
->looping
= true;
528 local
->pure_const_state
= IPA_NEITHER
;
531 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
532 switch (DECL_FUNCTION_CODE (callee_t
))
534 case BUILT_IN_LONGJMP
:
535 case BUILT_IN_NONLOCAL_GOTO
:
537 fprintf (dump_file
, " longjmp and nonlocal goto is not const/pure\n");
538 local
->pure_const_state
= IPA_NEITHER
;
539 local
->looping
= true;
546 /* When not in IPA mode, we can still handle self recursion. */
547 if (!ipa
&& callee_t
== current_function_decl
)
550 fprintf (dump_file
, " Recursive call can loop.\n");
551 local
->looping
= true;
553 /* Either callee is unknown or we are doing local analysis.
554 Look to see if there are any bits available for the callee (such as by
555 declaration or because it is builtin) and process solely on the basis of
559 enum pure_const_state_e call_state
;
561 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
564 fprintf (dump_file
, " can throw; looping\n");
565 local
->looping
= true;
567 if (possibly_throws_externally
)
571 fprintf (dump_file
, " can throw externally to lp %i\n",
572 lookup_stmt_eh_lp (call
));
574 fprintf (dump_file
, " callee:%s\n",
575 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t
)));
577 local
->can_throw
= true;
579 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
580 fprintf (dump_file
, " checking flags for call:");
581 state_from_flags (&call_state
, &call_looping
, flags
,
582 ((flags
& (ECF_NORETURN
| ECF_NOTHROW
))
583 == (ECF_NORETURN
| ECF_NOTHROW
))
584 || (!flag_exceptions
&& (flags
& ECF_NORETURN
)));
585 worse_state (&local
->pure_const_state
, &local
->looping
,
586 call_state
, call_looping
);
588 /* Direct functions calls are handled by IPA propagation. */
591 /* Wrapper around check_decl for loads in local more. */
594 check_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
597 check_decl ((funct_state
)data
, op
, false, false);
599 check_op ((funct_state
)data
, op
, false);
603 /* Wrapper around check_decl for stores in local more. */
606 check_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
609 check_decl ((funct_state
)data
, op
, true, false);
611 check_op ((funct_state
)data
, op
, true);
615 /* Wrapper around check_decl for loads in ipa mode. */
618 check_ipa_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
621 check_decl ((funct_state
)data
, op
, false, true);
623 check_op ((funct_state
)data
, op
, false);
627 /* Wrapper around check_decl for stores in ipa mode. */
630 check_ipa_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
633 check_decl ((funct_state
)data
, op
, true, true);
635 check_op ((funct_state
)data
, op
, true);
639 /* Look into pointer pointed to by GSIP and figure out what interesting side
642 check_stmt (gimple_stmt_iterator
*gsip
, funct_state local
, bool ipa
)
644 gimple stmt
= gsi_stmt (*gsip
);
646 if (is_gimple_debug (stmt
))
651 fprintf (dump_file
, " scanning: ");
652 print_gimple_stmt (dump_file
, stmt
, 0, 0);
655 if (gimple_has_volatile_ops (stmt
)
656 && !gimple_clobber_p (stmt
))
658 local
->pure_const_state
= IPA_NEITHER
;
660 fprintf (dump_file
, " Volatile stmt is not const/pure\n");
663 /* Look for loads and stores. */
664 walk_stmt_load_store_ops (stmt
, local
,
665 ipa
? check_ipa_load
: check_load
,
666 ipa
? check_ipa_store
: check_store
);
668 if (gimple_code (stmt
) != GIMPLE_CALL
669 && stmt_could_throw_p (stmt
))
671 if (cfun
->can_throw_non_call_exceptions
)
674 fprintf (dump_file
, " can throw; looping");
675 local
->looping
= true;
677 if (stmt_can_throw_external (stmt
))
680 fprintf (dump_file
, " can throw externally");
681 local
->can_throw
= true;
684 switch (gimple_code (stmt
))
687 check_call (local
, stmt
, ipa
);
690 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
691 /* Target of long jump. */
694 fprintf (dump_file
, " nonlocal label is not const/pure");
695 local
->pure_const_state
= IPA_NEITHER
;
699 if (gimple_asm_clobbers_memory_p (stmt
))
702 fprintf (dump_file
, " memory asm clobber is not const/pure");
703 /* Abandon all hope, ye who enter here. */
704 local
->pure_const_state
= IPA_NEITHER
;
706 if (gimple_asm_volatile_p (stmt
))
709 fprintf (dump_file
, " volatile is not const/pure");
710 /* Abandon all hope, ye who enter here. */
711 local
->pure_const_state
= IPA_NEITHER
;
712 local
->looping
= true;
721 /* This is the main routine for finding the reference patterns for
722 global variables within a function FN. */
725 analyze_function (struct cgraph_node
*fn
, bool ipa
)
727 tree decl
= fn
->symbol
.decl
;
728 tree old_decl
= current_function_decl
;
730 basic_block this_block
;
732 l
= XCNEW (struct funct_state_d
);
733 l
->pure_const_state
= IPA_CONST
;
734 l
->state_previously_known
= IPA_NEITHER
;
735 l
->looping_previously_known
= true;
737 l
->can_throw
= false;
738 state_from_flags (&l
->state_previously_known
, &l
->looping_previously_known
,
739 flags_from_decl_or_type (fn
->symbol
.decl
),
740 cgraph_node_cannot_return (fn
));
742 if (fn
->thunk
.thunk_p
|| fn
->alias
)
744 /* Thunk gets propagated through, so nothing interesting happens. */
751 fprintf (dump_file
, "\n\n local analysis of %s\n ",
752 cgraph_node_name (fn
));
755 push_cfun (DECL_STRUCT_FUNCTION (decl
));
756 current_function_decl
= decl
;
758 FOR_EACH_BB (this_block
)
760 gimple_stmt_iterator gsi
;
761 struct walk_stmt_info wi
;
763 memset (&wi
, 0, sizeof(wi
));
764 for (gsi
= gsi_start_bb (this_block
);
768 check_stmt (&gsi
, l
, ipa
);
769 if (l
->pure_const_state
== IPA_NEITHER
&& l
->looping
&& l
->can_throw
)
775 if (l
->pure_const_state
!= IPA_NEITHER
)
777 /* Const functions cannot have back edges (an
778 indication of possible infinite loop side
780 if (mark_dfs_back_edges ())
782 /* Preheaders are needed for SCEV to work.
783 Simple latches and recorded exits improve chances that loop will
784 proved to be finite in testcases such as in loop-15.c and loop-24.c */
785 loop_optimizer_init (LOOPS_NORMAL
786 | LOOPS_HAVE_RECORDED_EXITS
);
787 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
788 flow_loops_dump (dump_file
, NULL
, 0);
789 if (mark_irreducible_loops ())
792 fprintf (dump_file
, " has irreducible loops\n");
800 FOR_EACH_LOOP (li
, loop
, 0)
801 if (!finite_loop_p (loop
))
804 fprintf (dump_file
, " can not prove finiteness of loop %i\n", loop
->num
);
806 FOR_EACH_LOOP_BREAK (li
);
810 loop_optimizer_finalize ();
814 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
815 fprintf (dump_file
, " checking previously known:");
817 better_state (&l
->pure_const_state
, &l
->looping
,
818 l
->state_previously_known
,
819 l
->looping_previously_known
);
820 if (TREE_NOTHROW (decl
))
821 l
->can_throw
= false;
824 current_function_decl
= old_decl
;
828 fprintf (dump_file
, "Function is locally looping.\n");
830 fprintf (dump_file
, "Function is locally throwing.\n");
831 if (l
->pure_const_state
== IPA_CONST
)
832 fprintf (dump_file
, "Function is locally const.\n");
833 if (l
->pure_const_state
== IPA_PURE
)
834 fprintf (dump_file
, "Function is locally pure.\n");
839 /* Called when new function is inserted to callgraph late. */
841 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
843 if (cgraph_function_body_availability (node
) < AVAIL_OVERWRITABLE
)
845 /* There are some shared nodes, in particular the initializers on
846 static declarations. We do not need to scan them more than once
847 since all we would be interested in are the addressof
849 visited_nodes
= pointer_set_create ();
850 if (cgraph_function_body_availability (node
) > AVAIL_OVERWRITABLE
)
851 set_function_state (node
, analyze_function (node
, true));
852 pointer_set_destroy (visited_nodes
);
853 visited_nodes
= NULL
;
856 /* Called when new clone is inserted to callgraph late. */
859 duplicate_node_data (struct cgraph_node
*src
, struct cgraph_node
*dst
,
860 void *data ATTRIBUTE_UNUSED
)
862 if (has_function_state (src
))
864 funct_state l
= XNEW (struct funct_state_d
);
865 gcc_assert (!has_function_state (dst
));
866 memcpy (l
, get_function_state (src
), sizeof (*l
));
867 set_function_state (dst
, l
);
871 /* Called when new clone is inserted to callgraph late. */
874 remove_node_data (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
876 if (has_function_state (node
))
878 funct_state l
= get_function_state (node
);
879 if (l
!= &varying_state
)
881 set_function_state (node
, NULL
);
887 register_hooks (void)
889 static bool init_p
= false;
896 node_removal_hook_holder
=
897 cgraph_add_node_removal_hook (&remove_node_data
, NULL
);
898 node_duplication_hook_holder
=
899 cgraph_add_node_duplication_hook (&duplicate_node_data
, NULL
);
900 function_insertion_hook_holder
=
901 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
905 /* Analyze each function in the cgraph to see if it is locally PURE or
909 generate_summary (void)
911 struct cgraph_node
*node
;
915 /* There are some shared nodes, in particular the initializers on
916 static declarations. We do not need to scan them more than once
917 since all we would be interested in are the addressof
919 visited_nodes
= pointer_set_create ();
921 /* Process all of the functions.
923 We process AVAIL_OVERWRITABLE functions. We can not use the results
924 by default, but the info can be used at LTO with -fwhole-program or
925 when function got cloned and the clone is AVAILABLE. */
927 FOR_EACH_DEFINED_FUNCTION (node
)
928 if (cgraph_function_body_availability (node
) >= AVAIL_OVERWRITABLE
)
929 set_function_state (node
, analyze_function (node
, true));
931 pointer_set_destroy (visited_nodes
);
932 visited_nodes
= NULL
;
936 /* Serialize the ipa info for lto. */
939 pure_const_write_summary (void)
941 struct cgraph_node
*node
;
942 struct lto_simple_output_block
*ob
943 = lto_create_simple_output_block (LTO_section_ipa_pure_const
);
944 unsigned int count
= 0;
945 lto_symtab_encoder_iterator lsei
;
946 lto_symtab_encoder_t encoder
;
948 encoder
= lto_get_out_decl_state ()->symtab_node_encoder
;
950 for (lsei
= lsei_start_function_in_partition (encoder
); !lsei_end_p (lsei
);
951 lsei_next_function_in_partition (&lsei
))
953 node
= lsei_cgraph_node (lsei
);
954 if (node
->analyzed
&& has_function_state (node
))
958 streamer_write_uhwi_stream (ob
->main_stream
, count
);
960 /* Process all of the functions. */
961 for (lsei
= lsei_start_function_in_partition (encoder
); !lsei_end_p (lsei
);
962 lsei_next_function_in_partition (&lsei
))
964 node
= lsei_cgraph_node (lsei
);
965 if (node
->analyzed
&& has_function_state (node
))
970 lto_symtab_encoder_t encoder
;
972 fs
= get_function_state (node
);
974 encoder
= ob
->decl_state
->symtab_node_encoder
;
975 node_ref
= lto_symtab_encoder_encode (encoder
, (symtab_node
)node
);
976 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
978 /* Note that flags will need to be read in the opposite
979 order as we are pushing the bitflags into FLAGS. */
980 bp
= bitpack_create (ob
->main_stream
);
981 bp_pack_value (&bp
, fs
->pure_const_state
, 2);
982 bp_pack_value (&bp
, fs
->state_previously_known
, 2);
983 bp_pack_value (&bp
, fs
->looping_previously_known
, 1);
984 bp_pack_value (&bp
, fs
->looping
, 1);
985 bp_pack_value (&bp
, fs
->can_throw
, 1);
986 streamer_write_bitpack (&bp
);
990 lto_destroy_simple_output_block (ob
);
994 /* Deserialize the ipa info for lto. */
997 pure_const_read_summary (void)
999 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
1000 struct lto_file_decl_data
*file_data
;
1004 while ((file_data
= file_data_vec
[j
++]))
1008 struct lto_input_block
*ib
1009 = lto_create_simple_input_block (file_data
,
1010 LTO_section_ipa_pure_const
,
1015 unsigned int count
= streamer_read_uhwi (ib
);
1017 for (i
= 0; i
< count
; i
++)
1020 struct cgraph_node
*node
;
1021 struct bitpack_d bp
;
1023 lto_symtab_encoder_t encoder
;
1025 fs
= XCNEW (struct funct_state_d
);
1026 index
= streamer_read_uhwi (ib
);
1027 encoder
= file_data
->symtab_node_encoder
;
1028 node
= cgraph (lto_symtab_encoder_deref (encoder
, index
));
1029 set_function_state (node
, fs
);
1031 /* Note that the flags must be read in the opposite
1032 order in which they were written (the bitflags were
1033 pushed into FLAGS). */
1034 bp
= streamer_read_bitpack (ib
);
1035 fs
->pure_const_state
1036 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1037 fs
->state_previously_known
1038 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1039 fs
->looping_previously_known
= bp_unpack_value (&bp
, 1);
1040 fs
->looping
= bp_unpack_value (&bp
, 1);
1041 fs
->can_throw
= bp_unpack_value (&bp
, 1);
1044 int flags
= flags_from_decl_or_type (node
->symbol
.decl
);
1045 fprintf (dump_file
, "Read info for %s/%i ",
1046 cgraph_node_name (node
),
1048 if (flags
& ECF_CONST
)
1049 fprintf (dump_file
, " const");
1050 if (flags
& ECF_PURE
)
1051 fprintf (dump_file
, " pure");
1052 if (flags
& ECF_NOTHROW
)
1053 fprintf (dump_file
, " nothrow");
1054 fprintf (dump_file
, "\n pure const state: %s\n",
1055 pure_const_names
[fs
->pure_const_state
]);
1056 fprintf (dump_file
, " previously known state: %s\n",
1057 pure_const_names
[fs
->looping_previously_known
]);
1059 fprintf (dump_file
," function is locally looping\n");
1060 if (fs
->looping_previously_known
)
1061 fprintf (dump_file
," function is previously known looping\n");
1063 fprintf (dump_file
," function is locally throwing\n");
1067 lto_destroy_simple_input_block (file_data
,
1068 LTO_section_ipa_pure_const
,
1076 ignore_edge (struct cgraph_edge
*e
)
1078 return (!e
->can_throw_external
);
1081 /* Return true if NODE is self recursive function.
1082 ??? self recursive and indirectly recursive funcions should
1083 be the same, so this function seems unnecesary. */
1086 self_recursive_p (struct cgraph_node
*node
)
1088 struct cgraph_edge
*e
;
1089 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1090 if (cgraph_function_node (e
->callee
, NULL
) == node
)
1095 /* Produce transitive closure over the callgraph and compute pure/const
1099 propagate_pure_const (void)
1101 struct cgraph_node
*node
;
1102 struct cgraph_node
*w
;
1103 struct cgraph_node
**order
=
1104 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1107 struct ipa_dfs_info
* w_info
;
1109 order_pos
= ipa_reduced_postorder (order
, true, false, NULL
);
1112 dump_cgraph (dump_file
);
1113 ipa_print_order(dump_file
, "reduced", order
, order_pos
);
1116 /* Propagate the local information through the call graph to produce
1117 the global information. All the nodes within a cycle will have
1118 the same info so we collapse cycles first. Then we can do the
1119 propagation in one pass from the leaves to the roots. */
1120 for (i
= 0; i
< order_pos
; i
++ )
1122 enum pure_const_state_e pure_const_state
= IPA_CONST
;
1123 bool looping
= false;
1130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1131 fprintf (dump_file
, "Starting cycle\n");
1133 /* Find the worst state for any node in the cycle. */
1135 while (w
&& pure_const_state
!= IPA_NEITHER
)
1137 struct cgraph_edge
*e
;
1138 struct cgraph_edge
*ie
;
1140 struct ipa_ref
*ref
;
1142 funct_state w_l
= get_function_state (w
);
1143 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1144 fprintf (dump_file
, " Visiting %s/%i state:%s looping %i\n",
1145 cgraph_node_name (w
),
1147 pure_const_names
[w_l
->pure_const_state
],
1150 /* First merge in function body properties. */
1151 worse_state (&pure_const_state
, &looping
,
1152 w_l
->pure_const_state
, w_l
->looping
);
1153 if (pure_const_state
== IPA_NEITHER
)
1156 /* For overwritable nodes we can not assume anything. */
1157 if (cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1159 worse_state (&pure_const_state
, &looping
,
1160 w_l
->state_previously_known
,
1161 w_l
->looping_previously_known
);
1162 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1165 " Overwritable. state %s looping %i\n",
1166 pure_const_names
[w_l
->state_previously_known
],
1167 w_l
->looping_previously_known
);
1174 /* We consider recursive cycles as possibly infinite.
1175 This might be relaxed since infinite recursion leads to stack
1180 /* Now walk the edges and merge in callee properties. */
1181 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1183 enum availability avail
;
1184 struct cgraph_node
*y
= cgraph_function_node (e
->callee
, &avail
);
1185 enum pure_const_state_e edge_state
= IPA_CONST
;
1186 bool edge_looping
= false;
1188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1192 cgraph_node_name (e
->callee
),
1195 if (avail
> AVAIL_OVERWRITABLE
)
1197 funct_state y_l
= get_function_state (y
);
1198 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1201 " state:%s looping:%i\n",
1202 pure_const_names
[y_l
->pure_const_state
],
1205 if (y_l
->pure_const_state
> IPA_PURE
1206 && cgraph_edge_cannot_lead_to_return (e
))
1208 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1210 " Ignoring side effects"
1211 " -> pure, looping\n");
1212 edge_state
= IPA_PURE
;
1213 edge_looping
= true;
1217 edge_state
= y_l
->pure_const_state
;
1218 edge_looping
= y_l
->looping
;
1221 else if (special_builtin_state (&edge_state
, &edge_looping
,
1225 state_from_flags (&edge_state
, &edge_looping
,
1226 flags_from_decl_or_type (y
->symbol
.decl
),
1227 cgraph_edge_cannot_lead_to_return (e
));
1229 /* Merge the results with what we already know. */
1230 better_state (&edge_state
, &edge_looping
,
1231 w_l
->state_previously_known
,
1232 w_l
->looping_previously_known
);
1233 worse_state (&pure_const_state
, &looping
,
1234 edge_state
, edge_looping
);
1235 if (pure_const_state
== IPA_NEITHER
)
1238 if (pure_const_state
== IPA_NEITHER
)
1241 /* Now process the indirect call. */
1242 for (ie
= w
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1244 enum pure_const_state_e edge_state
= IPA_CONST
;
1245 bool edge_looping
= false;
1247 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1248 fprintf (dump_file
, " Indirect call");
1249 state_from_flags (&edge_state
, &edge_looping
,
1250 ie
->indirect_info
->ecf_flags
,
1251 cgraph_edge_cannot_lead_to_return (ie
));
1252 /* Merge the results with what we already know. */
1253 better_state (&edge_state
, &edge_looping
,
1254 w_l
->state_previously_known
,
1255 w_l
->looping_previously_known
);
1256 worse_state (&pure_const_state
, &looping
,
1257 edge_state
, edge_looping
);
1258 if (pure_const_state
== IPA_NEITHER
)
1261 if (pure_const_state
== IPA_NEITHER
)
1264 /* And finally all loads and stores. */
1265 for (i
= 0; ipa_ref_list_reference_iterate (&w
->symbol
.ref_list
, i
, ref
); i
++)
1267 enum pure_const_state_e ref_state
= IPA_CONST
;
1268 bool ref_looping
= false;
1272 /* readonly reads are safe. */
1273 if (TREE_READONLY (ipa_ref_varpool_node (ref
)->symbol
.decl
))
1275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1276 fprintf (dump_file
, " nonreadonly global var read\n");
1277 ref_state
= IPA_PURE
;
1280 if (ipa_ref_cannot_lead_to_return (ref
))
1282 ref_state
= IPA_NEITHER
;
1283 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1284 fprintf (dump_file
, " global var write\n");
1289 better_state (&ref_state
, &ref_looping
,
1290 w_l
->state_previously_known
,
1291 w_l
->looping_previously_known
);
1292 worse_state (&pure_const_state
, &looping
,
1293 ref_state
, ref_looping
);
1294 if (pure_const_state
== IPA_NEITHER
)
1297 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1298 w
= w_info
->next_cycle
;
1300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1301 fprintf (dump_file
, "Result %s looping %i\n",
1302 pure_const_names
[pure_const_state
],
1305 /* Copy back the region's pure_const_state which is shared by
1306 all nodes in the region. */
1310 funct_state w_l
= get_function_state (w
);
1311 enum pure_const_state_e this_state
= pure_const_state
;
1312 bool this_looping
= looping
;
1314 if (w_l
->state_previously_known
!= IPA_NEITHER
1315 && this_state
> w_l
->state_previously_known
)
1317 this_state
= w_l
->state_previously_known
;
1318 this_looping
|= w_l
->looping_previously_known
;
1320 if (!this_looping
&& self_recursive_p (w
))
1321 this_looping
= true;
1322 if (!w_l
->looping_previously_known
)
1323 this_looping
= false;
1325 /* All nodes within a cycle share the same info. */
1326 w_l
->pure_const_state
= this_state
;
1327 w_l
->looping
= this_looping
;
1332 if (!TREE_READONLY (w
->symbol
.decl
))
1334 warn_function_const (w
->symbol
.decl
, !this_looping
);
1336 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1337 this_looping
? "looping " : "",
1338 cgraph_node_name (w
));
1340 cgraph_set_const_flag (w
, true, this_looping
);
1344 if (!DECL_PURE_P (w
->symbol
.decl
))
1346 warn_function_pure (w
->symbol
.decl
, !this_looping
);
1348 fprintf (dump_file
, "Function found to be %spure: %s\n",
1349 this_looping
? "looping " : "",
1350 cgraph_node_name (w
));
1352 cgraph_set_pure_flag (w
, true, this_looping
);
1358 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1359 w
= w_info
->next_cycle
;
1363 ipa_free_postorder_info ();
1367 /* Produce transitive closure over the callgraph and compute nothrow
1371 propagate_nothrow (void)
1373 struct cgraph_node
*node
;
1374 struct cgraph_node
*w
;
1375 struct cgraph_node
**order
=
1376 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1379 struct ipa_dfs_info
* w_info
;
1381 order_pos
= ipa_reduced_postorder (order
, true, false, ignore_edge
);
1384 dump_cgraph (dump_file
);
1385 ipa_print_order (dump_file
, "reduced for nothrow", order
, order_pos
);
1388 /* Propagate the local information through the call graph to produce
1389 the global information. All the nodes within a cycle will have
1390 the same info so we collapse cycles first. Then we can do the
1391 propagation in one pass from the leaves to the roots. */
1392 for (i
= 0; i
< order_pos
; i
++ )
1394 bool can_throw
= false;
1400 /* Find the worst state for any node in the cycle. */
1404 struct cgraph_edge
*e
, *ie
;
1405 funct_state w_l
= get_function_state (w
);
1408 || cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1414 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1416 enum availability avail
;
1417 struct cgraph_node
*y
= cgraph_function_node (e
->callee
, &avail
);
1419 if (avail
> AVAIL_OVERWRITABLE
)
1421 funct_state y_l
= get_function_state (y
);
1425 if (y_l
->can_throw
&& !TREE_NOTHROW (w
->symbol
.decl
)
1426 && e
->can_throw_external
)
1429 else if (e
->can_throw_external
&& !TREE_NOTHROW (y
->symbol
.decl
))
1432 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1433 if (ie
->can_throw_external
)
1435 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1436 w
= w_info
->next_cycle
;
1439 /* Copy back the region's pure_const_state which is shared by
1440 all nodes in the region. */
1444 funct_state w_l
= get_function_state (w
);
1445 if (!can_throw
&& !TREE_NOTHROW (w
->symbol
.decl
))
1447 cgraph_set_nothrow_flag (w
, true);
1449 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1450 cgraph_node_name (w
));
1452 else if (can_throw
&& !TREE_NOTHROW (w
->symbol
.decl
))
1453 w_l
->can_throw
= true;
1454 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1455 w
= w_info
->next_cycle
;
1459 ipa_free_postorder_info ();
1464 /* Produce the global information by preforming a transitive closure
1465 on the local information that was produced by generate_summary. */
1470 struct cgraph_node
*node
;
1472 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1473 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
1474 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
1476 /* Nothrow makes more function to not lead to return and improve
1478 propagate_nothrow ();
1479 propagate_pure_const ();
1482 FOR_EACH_DEFINED_FUNCTION (node
)
1483 if (has_function_state (node
))
1484 free (get_function_state (node
));
1485 VEC_free (funct_state
, heap
, funct_state_vec
);
1491 gate_pure_const (void)
1493 return (flag_ipa_pure_const
1494 /* Don't bother doing anything if the program has errors. */
1498 struct ipa_opt_pass_d pass_ipa_pure_const
=
1502 "pure-const", /* name */
1503 gate_pure_const
, /* gate */
1504 propagate
, /* execute */
1507 0, /* static_pass_number */
1508 TV_IPA_PURE_CONST
, /* tv_id */
1509 0, /* properties_required */
1510 0, /* properties_provided */
1511 0, /* properties_destroyed */
1512 0, /* todo_flags_start */
1513 0 /* todo_flags_finish */
1515 generate_summary
, /* generate_summary */
1516 pure_const_write_summary
, /* write_summary */
1517 pure_const_read_summary
, /* read_summary */
1518 NULL
, /* write_optimization_summary */
1519 NULL
, /* read_optimization_summary */
1520 NULL
, /* stmt_fixup */
1522 NULL
, /* function_transform */
1523 NULL
/* variable_transform */
1526 /* Return true if function should be skipped for local pure const analysis. */
1529 skip_function_for_local_pure_const (struct cgraph_node
*node
)
1531 /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1532 we must not promote functions that are called by already processed functions. */
1534 if (function_called_by_processed_nodes_p ())
1537 fprintf (dump_file
, "Function called in recursive cycle; ignoring\n");
1540 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
1543 fprintf (dump_file
, "Function is not available or overwritable; not analyzing.\n");
1549 /* Simple local pass for pure const discovery reusing the analysis from
1550 ipa_pure_const. This pass is effective when executed together with
1551 other optimization passes in early optimization pass queue. */
1554 local_pure_const (void)
1556 bool changed
= false;
1559 struct cgraph_node
*node
;
1561 node
= cgraph_get_node (current_function_decl
);
1562 skip
= skip_function_for_local_pure_const (node
);
1563 if (!warn_suggest_attribute_const
1564 && !warn_suggest_attribute_pure
1568 l
= analyze_function (node
, false);
1570 /* Do NORETURN discovery. */
1571 if (!skip
&& !TREE_THIS_VOLATILE (current_function_decl
)
1572 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 0)
1574 warn_function_noreturn (cfun
->decl
);
1576 fprintf (dump_file
, "Function found to be noreturn: %s\n",
1577 current_function_name ());
1579 /* Update declaration and reduce profile to executed once. */
1580 TREE_THIS_VOLATILE (current_function_decl
) = 1;
1581 if (node
->frequency
> NODE_FREQUENCY_EXECUTED_ONCE
)
1582 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
1587 switch (l
->pure_const_state
)
1590 if (!TREE_READONLY (current_function_decl
))
1592 warn_function_const (current_function_decl
, !l
->looping
);
1595 cgraph_set_const_flag (node
, true, l
->looping
);
1599 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1600 l
->looping
? "looping " : "",
1601 current_function_name ());
1603 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1608 cgraph_set_const_flag (node
, true, false);
1612 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1613 current_function_name ());
1618 if (!DECL_PURE_P (current_function_decl
))
1622 cgraph_set_pure_flag (node
, true, l
->looping
);
1625 warn_function_pure (current_function_decl
, !l
->looping
);
1627 fprintf (dump_file
, "Function found to be %spure: %s\n",
1628 l
->looping
? "looping " : "",
1629 current_function_name ());
1631 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1636 cgraph_set_pure_flag (node
, true, false);
1640 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1641 current_function_name ());
1648 if (!l
->can_throw
&& !TREE_NOTHROW (current_function_decl
))
1650 cgraph_set_nothrow_flag (node
, true);
1653 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1654 current_function_name ());
1658 return execute_fixup_cfg ();
1663 struct gimple_opt_pass pass_local_pure_const
=
1667 "local-pure-const", /* name */
1668 gate_pure_const
, /* gate */
1669 local_pure_const
, /* execute */
1672 0, /* static_pass_number */
1673 TV_IPA_PURE_CONST
, /* tv_id */
1674 0, /* properties_required */
1675 0, /* properties_provided */
1676 0, /* properties_destroyed */
1677 0, /* todo_flags_start */
1678 0 /* todo_flags_finish */