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"
52 #include "diagnostic.h"
53 #include "gimple-pretty-print.h"
54 #include "langhooks.h"
56 #include "lto-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
))
191 = suggest_attribute (OPT_Wsuggest_attribute_noreturn
, decl
,
192 true, warned_about
, "noreturn");
194 /* Init the function state. */
199 free (funct_state_vec
);
203 /* Return true if we have a function state for NODE. */
206 has_function_state (struct cgraph_node
*node
)
209 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
211 return VEC_index (funct_state
, funct_state_vec
, node
->uid
) != NULL
;
214 /* Return the function state from NODE. */
216 static inline funct_state
217 get_function_state (struct cgraph_node
*node
)
220 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
221 || !VEC_index (funct_state
, funct_state_vec
, node
->uid
))
222 /* We might want to put correct previously_known state into varying. */
223 return &varying_state
;
224 return VEC_index (funct_state
, funct_state_vec
, node
->uid
);
227 /* Set the function state S for NODE. */
230 set_function_state (struct cgraph_node
*node
, funct_state s
)
233 || VEC_length (funct_state
, funct_state_vec
) <= (unsigned int)node
->uid
)
234 VEC_safe_grow_cleared (funct_state
, heap
, funct_state_vec
, node
->uid
+ 1);
235 VEC_replace (funct_state
, funct_state_vec
, node
->uid
, s
);
238 /* Check to see if the use (or definition when CHECKING_WRITE is true)
239 variable T is legal in a function that is either pure or const. */
242 check_decl (funct_state local
,
243 tree t
, bool checking_write
, bool ipa
)
245 /* Do not want to do anything with volatile except mark any
246 function that uses one to be not const or pure. */
247 if (TREE_THIS_VOLATILE (t
))
249 local
->pure_const_state
= IPA_NEITHER
;
251 fprintf (dump_file
, " Volatile operand is not const/pure");
255 /* Do not care about a local automatic that is not static. */
256 if (!TREE_STATIC (t
) && !DECL_EXTERNAL (t
))
259 /* If the variable has the "used" attribute, treat it as if it had a
260 been touched by the devil. */
261 if (DECL_PRESERVE_P (t
))
263 local
->pure_const_state
= IPA_NEITHER
;
265 fprintf (dump_file
, " Used static/global variable is not const/pure\n");
269 /* In IPA mode we are not interested in checking actual loads and stores;
270 they will be processed at propagation time using ipa_ref. */
274 /* Since we have dealt with the locals and params cases above, if we
275 are CHECKING_WRITE, this cannot be a pure or constant
279 local
->pure_const_state
= IPA_NEITHER
;
281 fprintf (dump_file
, " static/global memory write is not const/pure\n");
285 if (DECL_EXTERNAL (t
) || TREE_PUBLIC (t
))
287 /* Readonly reads are safe. */
288 if (TREE_READONLY (t
) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t
)))
289 return; /* Read of a constant, do not change the function state. */
293 fprintf (dump_file
, " global memory read is not const\n");
294 /* Just a regular read. */
295 if (local
->pure_const_state
== IPA_CONST
)
296 local
->pure_const_state
= IPA_PURE
;
301 /* Compilation level statics can be read if they are readonly
303 if (TREE_READONLY (t
))
307 fprintf (dump_file
, " static memory read is not const\n");
308 /* Just a regular read. */
309 if (local
->pure_const_state
== IPA_CONST
)
310 local
->pure_const_state
= IPA_PURE
;
315 /* Check to see if the use (or definition when CHECKING_WRITE is true)
316 variable T is legal in a function that is either pure or const. */
319 check_op (funct_state local
, tree t
, bool checking_write
)
321 t
= get_base_address (t
);
322 if (t
&& TREE_THIS_VOLATILE (t
))
324 local
->pure_const_state
= IPA_NEITHER
;
326 fprintf (dump_file
, " Volatile indirect ref is not const/pure\n");
330 && (INDIRECT_REF_P (t
) || TREE_CODE (t
) == MEM_REF
)
331 && TREE_CODE (TREE_OPERAND (t
, 0)) == SSA_NAME
332 && !ptr_deref_may_alias_global_p (TREE_OPERAND (t
, 0)))
335 fprintf (dump_file
, " Indirect ref to local memory is OK\n");
338 else if (checking_write
)
340 local
->pure_const_state
= IPA_NEITHER
;
342 fprintf (dump_file
, " Indirect ref write is not const/pure\n");
348 fprintf (dump_file
, " Indirect ref read is not const\n");
349 if (local
->pure_const_state
== IPA_CONST
)
350 local
->pure_const_state
= IPA_PURE
;
354 /* compute state based on ECF FLAGS and store to STATE and LOOPING. */
357 state_from_flags (enum pure_const_state_e
*state
, bool *looping
,
358 int flags
, bool cannot_lead_to_return
)
361 if (flags
& ECF_LOOPING_CONST_OR_PURE
)
364 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
365 fprintf (dump_file
, " looping");
367 if (flags
& ECF_CONST
)
370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
371 fprintf (dump_file
, " const\n");
373 else if (flags
& ECF_PURE
)
376 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
377 fprintf (dump_file
, " pure\n");
379 else if (cannot_lead_to_return
)
383 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
384 fprintf (dump_file
, " ignoring side effects->pure looping\n");
388 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
389 fprintf (dump_file
, " neihter\n");
390 *state
= IPA_NEITHER
;
395 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
396 into STATE and LOOPING better of the two variants.
397 Be sure to merge looping correctly. IPA_NEITHER functions
398 have looping 0 even if they don't have to return. */
401 better_state (enum pure_const_state_e
*state
, bool *looping
,
402 enum pure_const_state_e state2
, bool looping2
)
406 if (*state
== IPA_NEITHER
)
409 *looping
= MIN (*looping
, looping2
);
411 else if (state2
!= IPA_NEITHER
)
412 *looping
= MIN (*looping
, looping2
);
415 /* Merge STATE and STATE2 and LOOPING and LOOPING2 and store
416 into STATE and LOOPING worse of the two variants. */
419 worse_state (enum pure_const_state_e
*state
, bool *looping
,
420 enum pure_const_state_e state2
, bool looping2
)
422 *state
= MAX (*state
, state2
);
423 *looping
= MAX (*looping
, looping2
);
426 /* Recognize special cases of builtins that are by themselves not pure or const
427 but function using them is. */
429 special_builtin_state (enum pure_const_state_e
*state
, bool *looping
,
432 if (DECL_BUILT_IN_CLASS (callee
) == BUILT_IN_NORMAL
)
433 switch (DECL_FUNCTION_CODE (callee
))
435 case BUILT_IN_RETURN
:
436 case BUILT_IN_UNREACHABLE
:
437 case BUILT_IN_ALLOCA
:
438 case BUILT_IN_STACK_SAVE
:
439 case BUILT_IN_STACK_RESTORE
:
440 case BUILT_IN_EH_POINTER
:
441 case BUILT_IN_EH_FILTER
:
442 case BUILT_IN_UNWIND_RESUME
:
443 case BUILT_IN_CXA_END_CLEANUP
:
444 case BUILT_IN_EH_COPY_VALUES
:
445 case BUILT_IN_FRAME_ADDRESS
:
447 case BUILT_IN_APPLY_ARGS
:
451 case BUILT_IN_PREFETCH
:
459 /* Check the parameters of a function call to CALL_EXPR to see if
460 there are any references in the parameters that are not allowed for
461 pure or const functions. Also check to see if this is either an
462 indirect call, a call outside the compilation unit, or has special
463 attributes that may also effect the purity. The CALL_EXPR node for
464 the entire call expression. */
467 check_call (funct_state local
, gimple call
, bool ipa
)
469 int flags
= gimple_call_flags (call
);
470 tree callee_t
= gimple_call_fndecl (call
);
471 bool possibly_throws
= stmt_could_throw_p (call
);
472 bool possibly_throws_externally
= (possibly_throws
473 && stmt_can_throw_external (call
));
478 for (i
= 0; i
< gimple_num_ops (call
); i
++)
479 if (gimple_op (call
, i
)
480 && tree_could_throw_p (gimple_op (call
, i
)))
482 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
485 fprintf (dump_file
, " operand can throw; looping\n");
486 local
->looping
= true;
488 if (possibly_throws_externally
)
491 fprintf (dump_file
, " operand can throw externally\n");
492 local
->can_throw
= true;
497 /* The const and pure flags are set by a variety of places in the
498 compiler (including here). If someone has already set the flags
499 for the callee, (such as for some of the builtins) we will use
500 them, otherwise we will compute our own information.
502 Const and pure functions have less clobber effects than other
503 functions so we process these first. Otherwise if it is a call
504 outside the compilation unit or an indirect call we punt. This
505 leaves local calls which will be processed by following the call
509 enum pure_const_state_e call_state
;
512 if (special_builtin_state (&call_state
, &call_looping
, callee_t
))
514 worse_state (&local
->pure_const_state
, &local
->looping
,
515 call_state
, call_looping
);
518 /* When bad things happen to bad functions, they cannot be const
520 if (setjmp_call_p (callee_t
))
523 fprintf (dump_file
, " setjmp is not const/pure\n");
524 local
->looping
= true;
525 local
->pure_const_state
= IPA_NEITHER
;
528 if (DECL_BUILT_IN_CLASS (callee_t
) == BUILT_IN_NORMAL
)
529 switch (DECL_FUNCTION_CODE (callee_t
))
531 case BUILT_IN_LONGJMP
:
532 case BUILT_IN_NONLOCAL_GOTO
:
534 fprintf (dump_file
, " longjmp and nonlocal goto is not const/pure\n");
535 local
->pure_const_state
= IPA_NEITHER
;
536 local
->looping
= true;
543 /* When not in IPA mode, we can still handle self recursion. */
544 if (!ipa
&& callee_t
== current_function_decl
)
547 fprintf (dump_file
, " Recursive call can loop.\n");
548 local
->looping
= true;
550 /* Either callee is unknown or we are doing local analysis.
551 Look to see if there are any bits available for the callee (such as by
552 declaration or because it is builtin) and process solely on the basis of
556 enum pure_const_state_e call_state
;
558 if (possibly_throws
&& cfun
->can_throw_non_call_exceptions
)
561 fprintf (dump_file
, " can throw; looping\n");
562 local
->looping
= true;
564 if (possibly_throws_externally
)
568 fprintf (dump_file
, " can throw externally to lp %i\n",
569 lookup_stmt_eh_lp (call
));
571 fprintf (dump_file
, " callee:%s\n",
572 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t
)));
574 local
->can_throw
= true;
576 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
577 fprintf (dump_file
, " checking flags for call:");
578 state_from_flags (&call_state
, &call_looping
, flags
,
579 ((flags
& (ECF_NORETURN
| ECF_NOTHROW
))
580 == (ECF_NORETURN
| ECF_NOTHROW
))
581 || (!flag_exceptions
&& (flags
& ECF_NORETURN
)));
582 worse_state (&local
->pure_const_state
, &local
->looping
,
583 call_state
, call_looping
);
585 /* Direct functions calls are handled by IPA propagation. */
588 /* Wrapper around check_decl for loads in local more. */
591 check_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
594 check_decl ((funct_state
)data
, op
, false, false);
596 check_op ((funct_state
)data
, op
, false);
600 /* Wrapper around check_decl for stores in local more. */
603 check_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
606 check_decl ((funct_state
)data
, op
, true, false);
608 check_op ((funct_state
)data
, op
, true);
612 /* Wrapper around check_decl for loads in ipa mode. */
615 check_ipa_load (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
618 check_decl ((funct_state
)data
, op
, false, true);
620 check_op ((funct_state
)data
, op
, false);
624 /* Wrapper around check_decl for stores in ipa mode. */
627 check_ipa_store (gimple stmt ATTRIBUTE_UNUSED
, tree op
, void *data
)
630 check_decl ((funct_state
)data
, op
, true, true);
632 check_op ((funct_state
)data
, op
, true);
636 /* Look into pointer pointed to by GSIP and figure out what interesting side
639 check_stmt (gimple_stmt_iterator
*gsip
, funct_state local
, bool ipa
)
641 gimple stmt
= gsi_stmt (*gsip
);
643 if (is_gimple_debug (stmt
))
648 fprintf (dump_file
, " scanning: ");
649 print_gimple_stmt (dump_file
, stmt
, 0, 0);
652 if (gimple_has_volatile_ops (stmt
))
654 local
->pure_const_state
= IPA_NEITHER
;
656 fprintf (dump_file
, " Volatile stmt is not const/pure\n");
659 /* Look for loads and stores. */
660 walk_stmt_load_store_ops (stmt
, local
,
661 ipa
? check_ipa_load
: check_load
,
662 ipa
? check_ipa_store
: check_store
);
664 if (gimple_code (stmt
) != GIMPLE_CALL
665 && stmt_could_throw_p (stmt
))
667 if (cfun
->can_throw_non_call_exceptions
)
670 fprintf (dump_file
, " can throw; looping");
671 local
->looping
= true;
673 if (stmt_can_throw_external (stmt
))
676 fprintf (dump_file
, " can throw externally");
677 local
->can_throw
= true;
680 switch (gimple_code (stmt
))
683 check_call (local
, stmt
, ipa
);
686 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
687 /* Target of long jump. */
690 fprintf (dump_file
, " nonlocal label is not const/pure");
691 local
->pure_const_state
= IPA_NEITHER
;
695 if (gimple_asm_clobbers_memory_p (stmt
))
698 fprintf (dump_file
, " memory asm clobber is not const/pure");
699 /* Abandon all hope, ye who enter here. */
700 local
->pure_const_state
= IPA_NEITHER
;
702 if (gimple_asm_volatile_p (stmt
))
705 fprintf (dump_file
, " volatile is not const/pure");
706 /* Abandon all hope, ye who enter here. */
707 local
->pure_const_state
= IPA_NEITHER
;
708 local
->looping
= true;
717 /* This is the main routine for finding the reference patterns for
718 global variables within a function FN. */
721 analyze_function (struct cgraph_node
*fn
, bool ipa
)
723 tree decl
= fn
->decl
;
724 tree old_decl
= current_function_decl
;
726 basic_block this_block
;
728 l
= XCNEW (struct funct_state_d
);
729 l
->pure_const_state
= IPA_CONST
;
730 l
->state_previously_known
= IPA_NEITHER
;
731 l
->looping_previously_known
= true;
733 l
->can_throw
= false;
734 state_from_flags (&l
->state_previously_known
, &l
->looping_previously_known
,
735 flags_from_decl_or_type (fn
->decl
),
736 cgraph_node_cannot_return (fn
));
738 if (fn
->thunk
.thunk_p
)
740 /* Thunk gets propagated through, so nothing interesting happens. */
747 fprintf (dump_file
, "\n\n local analysis of %s\n ",
748 cgraph_node_name (fn
));
751 push_cfun (DECL_STRUCT_FUNCTION (decl
));
752 current_function_decl
= decl
;
754 FOR_EACH_BB (this_block
)
756 gimple_stmt_iterator gsi
;
757 struct walk_stmt_info wi
;
759 memset (&wi
, 0, sizeof(wi
));
760 for (gsi
= gsi_start_bb (this_block
);
764 check_stmt (&gsi
, l
, ipa
);
765 if (l
->pure_const_state
== IPA_NEITHER
&& l
->looping
&& l
->can_throw
)
771 if (l
->pure_const_state
!= IPA_NEITHER
)
773 /* Const functions cannot have back edges (an
774 indication of possible infinite loop side
776 if (mark_dfs_back_edges ())
778 /* Preheaders are needed for SCEV to work.
779 Simple latches and recorded exits improve chances that loop will
780 proved to be finite in testcases such as in loop-15.c and loop-24.c */
781 loop_optimizer_init (LOOPS_NORMAL
782 | LOOPS_HAVE_RECORDED_EXITS
);
783 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
784 flow_loops_dump (dump_file
, NULL
, 0);
785 if (mark_irreducible_loops ())
788 fprintf (dump_file
, " has irreducible loops\n");
796 FOR_EACH_LOOP (li
, loop
, 0)
797 if (!finite_loop_p (loop
))
800 fprintf (dump_file
, " can not prove finiteness of loop %i\n", loop
->num
);
806 loop_optimizer_finalize ();
810 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
811 fprintf (dump_file
, " checking previously known:");
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
;
824 fprintf (dump_file
, "Function is locally looping.\n");
826 fprintf (dump_file
, "Function is locally throwing.\n");
827 if (l
->pure_const_state
== IPA_CONST
)
828 fprintf (dump_file
, "Function is locally const.\n");
829 if (l
->pure_const_state
== IPA_PURE
)
830 fprintf (dump_file
, "Function is locally pure.\n");
835 /* Called when new function is inserted to callgraph late. */
837 add_new_function (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
839 if (cgraph_function_body_availability (node
) < AVAIL_OVERWRITABLE
)
841 /* There are some shared nodes, in particular the initializers on
842 static declarations. We do not need to scan them more than once
843 since all we would be interested in are the addressof
845 visited_nodes
= pointer_set_create ();
846 if (cgraph_function_body_availability (node
) > AVAIL_OVERWRITABLE
)
847 set_function_state (node
, analyze_function (node
, true));
848 pointer_set_destroy (visited_nodes
);
849 visited_nodes
= NULL
;
852 /* Called when new clone is inserted to callgraph late. */
855 duplicate_node_data (struct cgraph_node
*src
, struct cgraph_node
*dst
,
856 void *data ATTRIBUTE_UNUSED
)
858 if (has_function_state (src
))
860 funct_state l
= XNEW (struct funct_state_d
);
861 gcc_assert (!has_function_state (dst
));
862 memcpy (l
, get_function_state (src
), sizeof (*l
));
863 set_function_state (dst
, l
);
867 /* Called when new clone is inserted to callgraph late. */
870 remove_node_data (struct cgraph_node
*node
, void *data ATTRIBUTE_UNUSED
)
872 if (has_function_state (node
))
874 funct_state l
= get_function_state (node
);
875 if (l
!= &varying_state
)
877 set_function_state (node
, NULL
);
883 register_hooks (void)
885 static bool init_p
= false;
892 node_removal_hook_holder
=
893 cgraph_add_node_removal_hook (&remove_node_data
, NULL
);
894 node_duplication_hook_holder
=
895 cgraph_add_node_duplication_hook (&duplicate_node_data
, NULL
);
896 function_insertion_hook_holder
=
897 cgraph_add_function_insertion_hook (&add_new_function
, NULL
);
901 /* Analyze each function in the cgraph to see if it is locally PURE or
905 generate_summary (void)
907 struct cgraph_node
*node
;
911 /* There are some shared nodes, in particular the initializers on
912 static declarations. We do not need to scan them more than once
913 since all we would be interested in are the addressof
915 visited_nodes
= pointer_set_create ();
917 /* Process all of the functions.
919 We process AVAIL_OVERWRITABLE functions. We can not use the results
920 by default, but the info can be used at LTO with -fwhole-program or
921 when function got cloned and the clone is AVAILABLE. */
923 for (node
= cgraph_nodes
; node
; node
= node
->next
)
924 if (cgraph_function_body_availability (node
) >= AVAIL_OVERWRITABLE
)
925 set_function_state (node
, analyze_function (node
, true));
927 pointer_set_destroy (visited_nodes
);
928 visited_nodes
= NULL
;
932 /* Serialize the ipa info for lto. */
935 pure_const_write_summary (cgraph_node_set set
,
936 varpool_node_set vset ATTRIBUTE_UNUSED
)
938 struct cgraph_node
*node
;
939 struct lto_simple_output_block
*ob
940 = lto_create_simple_output_block (LTO_section_ipa_pure_const
);
941 unsigned int count
= 0;
942 cgraph_node_set_iterator csi
;
944 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
946 node
= csi_node (csi
);
947 if (node
->analyzed
&& has_function_state (node
))
951 lto_output_uleb128_stream (ob
->main_stream
, count
);
953 /* Process all of the functions. */
954 for (csi
= csi_start (set
); !csi_end_p (csi
); csi_next (&csi
))
956 node
= csi_node (csi
);
957 if (node
->analyzed
&& has_function_state (node
))
962 lto_cgraph_encoder_t encoder
;
964 fs
= get_function_state (node
);
966 encoder
= ob
->decl_state
->cgraph_node_encoder
;
967 node_ref
= lto_cgraph_encoder_encode (encoder
, node
);
968 lto_output_uleb128_stream (ob
->main_stream
, node_ref
);
970 /* Note that flags will need to be read in the opposite
971 order as we are pushing the bitflags into FLAGS. */
972 bp
= bitpack_create (ob
->main_stream
);
973 bp_pack_value (&bp
, fs
->pure_const_state
, 2);
974 bp_pack_value (&bp
, fs
->state_previously_known
, 2);
975 bp_pack_value (&bp
, fs
->looping_previously_known
, 1);
976 bp_pack_value (&bp
, fs
->looping
, 1);
977 bp_pack_value (&bp
, fs
->can_throw
, 1);
978 lto_output_bitpack (&bp
);
982 lto_destroy_simple_output_block (ob
);
986 /* Deserialize the ipa info for lto. */
989 pure_const_read_summary (void)
991 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
992 struct lto_file_decl_data
*file_data
;
996 while ((file_data
= file_data_vec
[j
++]))
1000 struct lto_input_block
*ib
1001 = lto_create_simple_input_block (file_data
,
1002 LTO_section_ipa_pure_const
,
1007 unsigned int count
= lto_input_uleb128 (ib
);
1009 for (i
= 0; i
< count
; i
++)
1012 struct cgraph_node
*node
;
1013 struct bitpack_d bp
;
1015 lto_cgraph_encoder_t encoder
;
1017 fs
= XCNEW (struct funct_state_d
);
1018 index
= lto_input_uleb128 (ib
);
1019 encoder
= file_data
->cgraph_node_encoder
;
1020 node
= lto_cgraph_encoder_deref (encoder
, index
);
1021 set_function_state (node
, fs
);
1023 /* Note that the flags must be read in the opposite
1024 order in which they were written (the bitflags were
1025 pushed into FLAGS). */
1026 bp
= lto_input_bitpack (ib
);
1027 fs
->pure_const_state
1028 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1029 fs
->state_previously_known
1030 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1031 fs
->looping_previously_known
= bp_unpack_value (&bp
, 1);
1032 fs
->looping
= bp_unpack_value (&bp
, 1);
1033 fs
->can_throw
= bp_unpack_value (&bp
, 1);
1036 int flags
= flags_from_decl_or_type (node
->decl
);
1037 fprintf (dump_file
, "Read info for %s/%i ",
1038 cgraph_node_name (node
),
1040 if (flags
& ECF_CONST
)
1041 fprintf (dump_file
, " const");
1042 if (flags
& ECF_PURE
)
1043 fprintf (dump_file
, " pure");
1044 if (flags
& ECF_NOTHROW
)
1045 fprintf (dump_file
, " nothrow");
1046 fprintf (dump_file
, "\n pure const state: %s\n",
1047 pure_const_names
[fs
->pure_const_state
]);
1048 fprintf (dump_file
, " previously known state: %s\n",
1049 pure_const_names
[fs
->looping_previously_known
]);
1051 fprintf (dump_file
," function is locally looping\n");
1052 if (fs
->looping_previously_known
)
1053 fprintf (dump_file
," function is previously known looping\n");
1055 fprintf (dump_file
," function is locally throwing\n");
1059 lto_destroy_simple_input_block (file_data
,
1060 LTO_section_ipa_pure_const
,
1068 ignore_edge (struct cgraph_edge
*e
)
1070 return (!e
->can_throw_external
);
1073 /* Return true if NODE is self recursive function. */
1076 self_recursive_p (struct cgraph_node
*node
)
1078 struct cgraph_edge
*e
;
1079 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1080 if (e
->callee
== node
)
1085 /* Produce transitive closure over the callgraph and compute pure/const
1089 propagate_pure_const (void)
1091 struct cgraph_node
*node
;
1092 struct cgraph_node
*w
;
1093 struct cgraph_node
**order
=
1094 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1097 struct ipa_dfs_info
* w_info
;
1099 order_pos
= ipa_reduced_postorder (order
, true, false, NULL
);
1102 dump_cgraph (dump_file
);
1103 ipa_print_order(dump_file
, "reduced", order
, order_pos
);
1106 /* Propagate the local information thru the call graph to produce
1107 the global information. All the nodes within a cycle will have
1108 the same info so we collapse cycles first. Then we can do the
1109 propagation in one pass from the leaves to the roots. */
1110 for (i
= 0; i
< order_pos
; i
++ )
1112 enum pure_const_state_e pure_const_state
= IPA_CONST
;
1113 bool looping
= false;
1117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1118 fprintf (dump_file
, "Starting cycle\n");
1120 /* Find the worst state for any node in the cycle. */
1122 while (w
&& pure_const_state
!= IPA_NEITHER
)
1124 struct cgraph_edge
*e
;
1125 struct cgraph_edge
*ie
;
1127 struct ipa_ref
*ref
;
1129 funct_state w_l
= get_function_state (w
);
1130 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1131 fprintf (dump_file
, " Visiting %s/%i state:%s looping %i\n",
1132 cgraph_node_name (w
),
1134 pure_const_names
[w_l
->pure_const_state
],
1137 /* First merge in function body properties. */
1138 worse_state (&pure_const_state
, &looping
,
1139 w_l
->pure_const_state
, w_l
->looping
);
1140 if (pure_const_state
== IPA_NEITHER
)
1143 /* For overwritable nodes we can not assume anything. */
1144 if (cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1146 worse_state (&pure_const_state
, &looping
,
1147 w_l
->state_previously_known
,
1148 w_l
->looping_previously_known
);
1149 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1152 " Overwritable. state %s looping %i\n",
1153 pure_const_names
[w_l
->state_previously_known
],
1154 w_l
->looping_previously_known
);
1161 /* We consider recursive cycles as possibly infinite.
1162 This might be relaxed since infinite recursion leads to stack
1167 /* Now walk the edges and merge in callee properties. */
1168 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1170 struct cgraph_node
*y
= e
->callee
;
1171 enum pure_const_state_e edge_state
= IPA_CONST
;
1172 bool edge_looping
= false;
1174 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1178 cgraph_node_name (e
->callee
),
1181 if (cgraph_function_body_availability (y
) > AVAIL_OVERWRITABLE
)
1183 funct_state y_l
= get_function_state (y
);
1184 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1187 " state:%s looping:%i\n",
1188 pure_const_names
[y_l
->pure_const_state
],
1191 if (y_l
->pure_const_state
> IPA_PURE
1192 && cgraph_edge_cannot_lead_to_return (e
))
1194 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1196 " Ignoring side effects"
1197 " -> pure, looping\n");
1198 edge_state
= IPA_PURE
;
1199 edge_looping
= true;
1203 edge_state
= y_l
->pure_const_state
;
1204 edge_looping
= y_l
->looping
;
1207 else if (special_builtin_state (&edge_state
, &edge_looping
,
1211 state_from_flags (&edge_state
, &edge_looping
,
1212 flags_from_decl_or_type (y
->decl
),
1213 cgraph_edge_cannot_lead_to_return (e
));
1215 /* Merge the results with what we already know. */
1216 better_state (&edge_state
, &edge_looping
,
1217 w_l
->state_previously_known
,
1218 w_l
->looping_previously_known
);
1219 worse_state (&pure_const_state
, &looping
,
1220 edge_state
, edge_looping
);
1221 if (pure_const_state
== IPA_NEITHER
)
1224 if (pure_const_state
== IPA_NEITHER
)
1227 /* Now process the indirect call. */
1228 for (ie
= w
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1230 enum pure_const_state_e edge_state
= IPA_CONST
;
1231 bool edge_looping
= false;
1233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1234 fprintf (dump_file
, " Indirect call");
1235 state_from_flags (&edge_state
, &edge_looping
,
1236 ie
->indirect_info
->ecf_flags
,
1237 cgraph_edge_cannot_lead_to_return (ie
));
1238 /* Merge the results with what we already know. */
1239 better_state (&edge_state
, &edge_looping
,
1240 w_l
->state_previously_known
,
1241 w_l
->looping_previously_known
);
1242 worse_state (&pure_const_state
, &looping
,
1243 edge_state
, edge_looping
);
1244 if (pure_const_state
== IPA_NEITHER
)
1247 if (pure_const_state
== IPA_NEITHER
)
1250 /* And finally all loads and stores. */
1251 for (i
= 0; ipa_ref_list_reference_iterate (&w
->ref_list
, i
, ref
); i
++)
1253 enum pure_const_state_e ref_state
= IPA_CONST
;
1254 bool ref_looping
= false;
1258 /* readonly reads are safe. */
1259 if (TREE_READONLY (ipa_ref_varpool_node (ref
)->decl
))
1261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1262 fprintf (dump_file
, " nonreadonly global var read\n");
1263 ref_state
= IPA_PURE
;
1266 if (ipa_ref_cannot_lead_to_return (ref
))
1268 ref_state
= IPA_NEITHER
;
1269 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1270 fprintf (dump_file
, " global var write\n");
1275 better_state (&ref_state
, &ref_looping
,
1276 w_l
->state_previously_known
,
1277 w_l
->looping_previously_known
);
1278 worse_state (&pure_const_state
, &looping
,
1279 ref_state
, ref_looping
);
1280 if (pure_const_state
== IPA_NEITHER
)
1283 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1284 w
= w_info
->next_cycle
;
1286 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1287 fprintf (dump_file
, "Result %s looping %i\n",
1288 pure_const_names
[pure_const_state
],
1291 /* Copy back the region's pure_const_state which is shared by
1292 all nodes in the region. */
1296 funct_state w_l
= get_function_state (w
);
1297 enum pure_const_state_e this_state
= pure_const_state
;
1298 bool this_looping
= looping
;
1300 if (w_l
->state_previously_known
!= IPA_NEITHER
1301 && this_state
> w_l
->state_previously_known
)
1303 this_state
= w_l
->state_previously_known
;
1304 this_looping
|= w_l
->looping_previously_known
;
1306 if (!this_looping
&& self_recursive_p (w
))
1307 this_looping
= true;
1308 if (!w_l
->looping_previously_known
)
1309 this_looping
= false;
1311 /* All nodes within a cycle share the same info. */
1312 w_l
->pure_const_state
= this_state
;
1313 w_l
->looping
= this_looping
;
1318 if (!TREE_READONLY (w
->decl
))
1320 warn_function_const (w
->decl
, !this_looping
);
1322 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1323 this_looping
? "looping " : "",
1324 cgraph_node_name (w
));
1326 cgraph_set_const_flag (w
, true, this_looping
);
1330 if (!DECL_PURE_P (w
->decl
))
1332 warn_function_pure (w
->decl
, !this_looping
);
1334 fprintf (dump_file
, "Function found to be %spure: %s\n",
1335 this_looping
? "looping " : "",
1336 cgraph_node_name (w
));
1338 cgraph_set_pure_flag (w
, true, this_looping
);
1344 w_info
= (struct ipa_dfs_info
*) w
->aux
;
1345 w
= w_info
->next_cycle
;
1349 ipa_free_postorder_info ();
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_reduced_postorder (order
, true, false, ignore_edge
);
1370 dump_cgraph (dump_file
);
1371 ipa_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
;
1444 ipa_free_postorder_info ();
1449 /* Produce the global information by preforming a transitive closure
1450 on the local information that was produced by generate_summary. */
1455 struct cgraph_node
*node
;
1457 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1458 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
1459 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
1461 /* Nothrow makes more function to not lead to return and improve
1463 propagate_nothrow ();
1464 propagate_pure_const ();
1467 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1468 if (has_function_state (node
))
1469 free (get_function_state (node
));
1470 VEC_free (funct_state
, heap
, funct_state_vec
);
1476 gate_pure_const (void)
1478 return (flag_ipa_pure_const
1479 /* Don't bother doing anything if the program has errors. */
1483 struct ipa_opt_pass_d pass_ipa_pure_const
=
1487 "pure-const", /* name */
1488 gate_pure_const
, /* gate */
1489 propagate
, /* execute */
1492 0, /* static_pass_number */
1493 TV_IPA_PURE_CONST
, /* tv_id */
1494 0, /* properties_required */
1495 0, /* properties_provided */
1496 0, /* properties_destroyed */
1497 0, /* todo_flags_start */
1498 0 /* todo_flags_finish */
1500 generate_summary
, /* generate_summary */
1501 pure_const_write_summary
, /* write_summary */
1502 pure_const_read_summary
, /* read_summary */
1503 NULL
, /* write_optimization_summary */
1504 NULL
, /* read_optimization_summary */
1505 NULL
, /* stmt_fixup */
1507 NULL
, /* function_transform */
1508 NULL
/* variable_transform */
1511 /* Return true if function should be skipped for local pure const analysis. */
1514 skip_function_for_local_pure_const (struct cgraph_node
*node
)
1516 /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1517 we must not promote functions that are called by already processed functions. */
1519 if (function_called_by_processed_nodes_p ())
1522 fprintf (dump_file
, "Function called in recursive cycle; ignoring\n");
1525 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
1528 fprintf (dump_file
, "Function is not available or overwritable; not analyzing.\n");
1534 /* Simple local pass for pure const discovery reusing the analysis from
1535 ipa_pure_const. This pass is effective when executed together with
1536 other optimization passes in early optimization pass queue. */
1539 local_pure_const (void)
1541 bool changed
= false;
1544 struct cgraph_node
*node
;
1546 node
= cgraph_get_node (current_function_decl
);
1547 skip
= skip_function_for_local_pure_const (node
);
1548 if (!warn_suggest_attribute_const
1549 && !warn_suggest_attribute_pure
1553 l
= analyze_function (node
, false);
1555 /* Do NORETURN discovery. */
1556 if (!skip
&& !TREE_THIS_VOLATILE (current_function_decl
)
1557 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 0)
1559 warn_function_noreturn (cfun
->decl
);
1561 fprintf (dump_file
, "Function found to be noreturn: %s\n",
1562 lang_hooks
.decl_printable_name (current_function_decl
, 2));
1564 /* Update declaration and reduce profile to executed once. */
1565 TREE_THIS_VOLATILE (current_function_decl
) = 1;
1566 if (node
->frequency
> NODE_FREQUENCY_EXECUTED_ONCE
)
1567 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
1572 switch (l
->pure_const_state
)
1575 if (!TREE_READONLY (current_function_decl
))
1577 warn_function_const (current_function_decl
, !l
->looping
);
1580 cgraph_set_const_flag (node
, true, l
->looping
);
1584 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1585 l
->looping
? "looping " : "",
1586 lang_hooks
.decl_printable_name (current_function_decl
,
1589 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1594 cgraph_set_const_flag (node
, true, false);
1598 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1599 lang_hooks
.decl_printable_name (current_function_decl
,
1605 if (!DECL_PURE_P (current_function_decl
))
1609 cgraph_set_pure_flag (node
, true, l
->looping
);
1612 warn_function_pure (current_function_decl
, !l
->looping
);
1614 fprintf (dump_file
, "Function found to be %spure: %s\n",
1615 l
->looping
? "looping " : "",
1616 lang_hooks
.decl_printable_name (current_function_decl
,
1619 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1624 cgraph_set_pure_flag (node
, true, false);
1628 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1629 lang_hooks
.decl_printable_name (current_function_decl
,
1637 if (!l
->can_throw
&& !TREE_NOTHROW (current_function_decl
))
1639 struct cgraph_edge
*e
;
1641 cgraph_set_nothrow_flag (node
, true);
1642 for (e
= node
->callers
; e
; e
= e
->next_caller
)
1643 e
->can_throw_external
= false;
1646 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1647 lang_hooks
.decl_printable_name (current_function_decl
,
1652 return execute_fixup_cfg ();
1657 struct gimple_opt_pass pass_local_pure_const
=
1661 "local-pure-const", /* name */
1662 gate_pure_const
, /* gate */
1663 local_pure_const
, /* execute */
1666 0, /* static_pass_number */
1667 TV_IPA_PURE_CONST
, /* tv_id */
1668 0, /* properties_required */
1669 0, /* properties_provided */
1670 0, /* properties_destroyed */
1671 0, /* todo_flags_start */
1672 0 /* todo_flags_finish */