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 static vec
<funct_state
> funct_state_vec
;
112 /* Holders of ipa cgraph hooks: */
113 static struct cgraph_node_hook_list
*function_insertion_hook_holder
;
114 static struct cgraph_2node_hook_list
*node_duplication_hook_holder
;
115 static struct cgraph_node_hook_list
*node_removal_hook_holder
;
117 /* Try to guess if function body will always be visible to compiler
118 when compiling the call and whether compiler will be able
119 to propagate the information by itself. */
122 function_always_visible_to_compiler_p (tree decl
)
124 return (!TREE_PUBLIC (decl
) || DECL_DECLARED_INLINE_P (decl
));
127 /* Emit suggestion about attribute ATTRIB_NAME for DECL. KNOWN_FINITE
128 is true if the function is known to be finite. The diagnostic is
129 controlled by OPTION. WARNED_ABOUT is a pointer_set unique for
130 OPTION, this function may initialize it and it is always returned
133 static struct pointer_set_t
*
134 suggest_attribute (int option
, tree decl
, bool known_finite
,
135 struct pointer_set_t
*warned_about
,
136 const char * attrib_name
)
138 if (!option_enabled (option
, &global_options
))
140 if (TREE_THIS_VOLATILE (decl
)
141 || (known_finite
&& function_always_visible_to_compiler_p (decl
)))
145 warned_about
= pointer_set_create ();
146 if (pointer_set_contains (warned_about
, decl
))
148 pointer_set_insert (warned_about
, decl
);
149 warning_at (DECL_SOURCE_LOCATION (decl
),
152 ? _("function might be candidate for attribute %<%s%>")
153 : _("function might be candidate for attribute %<%s%>"
154 " if it is known to return normally"), attrib_name
);
158 /* Emit suggestion about __attribute_((pure)) for DECL. KNOWN_FINITE
159 is true if the function is known to be finite. */
162 warn_function_pure (tree decl
, bool known_finite
)
164 static struct pointer_set_t
*warned_about
;
167 = suggest_attribute (OPT_Wsuggest_attribute_pure
, decl
,
168 known_finite
, warned_about
, "pure");
171 /* Emit suggestion about __attribute_((const)) for DECL. KNOWN_FINITE
172 is true if the function is known to be finite. */
175 warn_function_const (tree decl
, bool known_finite
)
177 static struct pointer_set_t
*warned_about
;
179 = suggest_attribute (OPT_Wsuggest_attribute_const
, decl
,
180 known_finite
, warned_about
, "const");
184 warn_function_noreturn (tree decl
)
186 static struct pointer_set_t
*warned_about
;
187 if (!lang_hooks
.missing_noreturn_ok_p (decl
)
188 && targetm
.warn_func_return (decl
))
190 = suggest_attribute (OPT_Wsuggest_attribute_noreturn
, decl
,
191 true, warned_about
, "noreturn");
194 /* Init the function state. */
199 funct_state_vec
.release ();
203 /* Return true if we have a function state for NODE. */
206 has_function_state (struct cgraph_node
*node
)
208 if (!funct_state_vec
.exists ()
209 || funct_state_vec
.length () <= (unsigned int)node
->uid
)
211 return 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
)
219 if (!funct_state_vec
.exists ()
220 || funct_state_vec
.length () <= (unsigned int)node
->uid
221 || !funct_state_vec
[node
->uid
])
222 /* We might want to put correct previously_known state into varying. */
223 return &varying_state
;
224 return funct_state_vec
[node
->uid
];
227 /* Set the function state S for NODE. */
230 set_function_state (struct cgraph_node
*node
, funct_state s
)
232 if (!funct_state_vec
.exists ()
233 || funct_state_vec
.length () <= (unsigned int)node
->uid
)
234 funct_state_vec
.safe_grow_cleared (node
->uid
+ 1);
235 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
, " neither\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_ALLOCA_WITH_ALIGN
:
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_builtin_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 callee 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
);
644 if (is_gimple_debug (stmt
))
649 fprintf (dump_file
, " scanning: ");
650 print_gimple_stmt (dump_file
, stmt
, 0, 0);
653 if (gimple_has_volatile_ops (stmt
)
654 && !gimple_clobber_p (stmt
))
656 local
->pure_const_state
= IPA_NEITHER
;
658 fprintf (dump_file
, " Volatile stmt is not const/pure\n");
661 /* Look for loads and stores. */
662 walk_stmt_load_store_ops (stmt
, local
,
663 ipa
? check_ipa_load
: check_load
,
664 ipa
? check_ipa_store
: check_store
);
666 if (gimple_code (stmt
) != GIMPLE_CALL
667 && stmt_could_throw_p (stmt
))
669 if (cfun
->can_throw_non_call_exceptions
)
672 fprintf (dump_file
, " can throw; looping\n");
673 local
->looping
= true;
675 if (stmt_can_throw_external (stmt
))
678 fprintf (dump_file
, " can throw externally\n");
679 local
->can_throw
= true;
683 fprintf (dump_file
, " can throw\n");
685 switch (gimple_code (stmt
))
688 check_call (local
, stmt
, ipa
);
691 if (DECL_NONLOCAL (gimple_label_label (stmt
)))
692 /* Target of long jump. */
695 fprintf (dump_file
, " nonlocal label is not const/pure\n");
696 local
->pure_const_state
= IPA_NEITHER
;
700 if (gimple_asm_clobbers_memory_p (stmt
))
703 fprintf (dump_file
, " memory asm clobber is not const/pure\n");
704 /* Abandon all hope, ye who enter here. */
705 local
->pure_const_state
= IPA_NEITHER
;
707 if (gimple_asm_volatile_p (stmt
))
710 fprintf (dump_file
, " volatile is not const/pure\n");
711 /* Abandon all hope, ye who enter here. */
712 local
->pure_const_state
= IPA_NEITHER
;
713 local
->looping
= true;
722 /* This is the main routine for finding the reference patterns for
723 global variables within a function FN. */
726 analyze_function (struct cgraph_node
*fn
, bool ipa
)
728 tree decl
= fn
->symbol
.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
));
757 FOR_EACH_BB (this_block
)
759 gimple_stmt_iterator gsi
;
760 struct walk_stmt_info wi
;
762 memset (&wi
, 0, sizeof(wi
));
763 for (gsi
= gsi_start_bb (this_block
);
767 check_stmt (&gsi
, l
, ipa
);
768 if (l
->pure_const_state
== IPA_NEITHER
&& l
->looping
&& l
->can_throw
)
774 if (l
->pure_const_state
!= IPA_NEITHER
)
776 /* Const functions cannot have back edges (an
777 indication of possible infinite loop side
779 if (mark_dfs_back_edges ())
781 /* Preheaders are needed for SCEV to work.
782 Simple latches and recorded exits improve chances that loop will
783 proved to be finite in testcases such as in loop-15.c and loop-24.c */
784 loop_optimizer_init (LOOPS_NORMAL
785 | LOOPS_HAVE_RECORDED_EXITS
);
786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
787 flow_loops_dump (dump_file
, NULL
, 0);
788 if (mark_irreducible_loops ())
791 fprintf (dump_file
, " has irreducible loops\n");
799 FOR_EACH_LOOP (li
, loop
, 0)
800 if (!finite_loop_p (loop
))
803 fprintf (dump_file
, " can not prove finiteness of loop %i\n", loop
->num
);
805 FOR_EACH_LOOP_BREAK (li
);
809 loop_optimizer_finalize ();
813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
814 fprintf (dump_file
, " checking previously known:");
816 better_state (&l
->pure_const_state
, &l
->looping
,
817 l
->state_previously_known
,
818 l
->looping_previously_known
);
819 if (TREE_NOTHROW (decl
))
820 l
->can_throw
= false;
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 cloned and the clone is AVAILABLE. */
925 FOR_EACH_DEFINED_FUNCTION (node
)
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 (void)
939 struct cgraph_node
*node
;
940 struct lto_simple_output_block
*ob
941 = lto_create_simple_output_block (LTO_section_ipa_pure_const
);
942 unsigned int count
= 0;
943 lto_symtab_encoder_iterator lsei
;
944 lto_symtab_encoder_t encoder
;
946 encoder
= lto_get_out_decl_state ()->symtab_node_encoder
;
948 for (lsei
= lsei_start_function_in_partition (encoder
); !lsei_end_p (lsei
);
949 lsei_next_function_in_partition (&lsei
))
951 node
= lsei_cgraph_node (lsei
);
952 if (node
->analyzed
&& has_function_state (node
))
956 streamer_write_uhwi_stream (ob
->main_stream
, count
);
958 /* Process all of the functions. */
959 for (lsei
= lsei_start_function_in_partition (encoder
); !lsei_end_p (lsei
);
960 lsei_next_function_in_partition (&lsei
))
962 node
= lsei_cgraph_node (lsei
);
963 if (node
->analyzed
&& has_function_state (node
))
968 lto_symtab_encoder_t encoder
;
970 fs
= get_function_state (node
);
972 encoder
= ob
->decl_state
->symtab_node_encoder
;
973 node_ref
= lto_symtab_encoder_encode (encoder
, (symtab_node
)node
);
974 streamer_write_uhwi_stream (ob
->main_stream
, node_ref
);
976 /* Note that flags will need to be read in the opposite
977 order as we are pushing the bitflags into FLAGS. */
978 bp
= bitpack_create (ob
->main_stream
);
979 bp_pack_value (&bp
, fs
->pure_const_state
, 2);
980 bp_pack_value (&bp
, fs
->state_previously_known
, 2);
981 bp_pack_value (&bp
, fs
->looping_previously_known
, 1);
982 bp_pack_value (&bp
, fs
->looping
, 1);
983 bp_pack_value (&bp
, fs
->can_throw
, 1);
984 streamer_write_bitpack (&bp
);
988 lto_destroy_simple_output_block (ob
);
992 /* Deserialize the ipa info for lto. */
995 pure_const_read_summary (void)
997 struct lto_file_decl_data
**file_data_vec
= lto_get_file_decl_data ();
998 struct lto_file_decl_data
*file_data
;
1002 while ((file_data
= file_data_vec
[j
++]))
1006 struct lto_input_block
*ib
1007 = lto_create_simple_input_block (file_data
,
1008 LTO_section_ipa_pure_const
,
1013 unsigned int count
= streamer_read_uhwi (ib
);
1015 for (i
= 0; i
< count
; i
++)
1018 struct cgraph_node
*node
;
1019 struct bitpack_d bp
;
1021 lto_symtab_encoder_t encoder
;
1023 fs
= XCNEW (struct funct_state_d
);
1024 index
= streamer_read_uhwi (ib
);
1025 encoder
= file_data
->symtab_node_encoder
;
1026 node
= cgraph (lto_symtab_encoder_deref (encoder
, index
));
1027 set_function_state (node
, fs
);
1029 /* Note that the flags must be read in the opposite
1030 order in which they were written (the bitflags were
1031 pushed into FLAGS). */
1032 bp
= streamer_read_bitpack (ib
);
1033 fs
->pure_const_state
1034 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1035 fs
->state_previously_known
1036 = (enum pure_const_state_e
) bp_unpack_value (&bp
, 2);
1037 fs
->looping_previously_known
= bp_unpack_value (&bp
, 1);
1038 fs
->looping
= bp_unpack_value (&bp
, 1);
1039 fs
->can_throw
= bp_unpack_value (&bp
, 1);
1042 int flags
= flags_from_decl_or_type (node
->symbol
.decl
);
1043 fprintf (dump_file
, "Read info for %s/%i ",
1044 cgraph_node_name (node
),
1046 if (flags
& ECF_CONST
)
1047 fprintf (dump_file
, " const");
1048 if (flags
& ECF_PURE
)
1049 fprintf (dump_file
, " pure");
1050 if (flags
& ECF_NOTHROW
)
1051 fprintf (dump_file
, " nothrow");
1052 fprintf (dump_file
, "\n pure const state: %s\n",
1053 pure_const_names
[fs
->pure_const_state
]);
1054 fprintf (dump_file
, " previously known state: %s\n",
1055 pure_const_names
[fs
->looping_previously_known
]);
1057 fprintf (dump_file
," function is locally looping\n");
1058 if (fs
->looping_previously_known
)
1059 fprintf (dump_file
," function is previously known looping\n");
1061 fprintf (dump_file
," function is locally throwing\n");
1065 lto_destroy_simple_input_block (file_data
,
1066 LTO_section_ipa_pure_const
,
1074 ignore_edge (struct cgraph_edge
*e
)
1076 return (!e
->can_throw_external
);
1079 /* Return true if NODE is self recursive function.
1080 ??? self recursive and indirectly recursive funcions should
1081 be the same, so this function seems unnecesary. */
1084 self_recursive_p (struct cgraph_node
*node
)
1086 struct cgraph_edge
*e
;
1087 for (e
= node
->callees
; e
; e
= e
->next_callee
)
1088 if (cgraph_function_node (e
->callee
, NULL
) == node
)
1093 /* Produce transitive closure over the callgraph and compute pure/const
1097 propagate_pure_const (void)
1099 struct cgraph_node
*node
;
1100 struct cgraph_node
*w
;
1101 struct cgraph_node
**order
=
1102 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1105 struct ipa_dfs_info
* w_info
;
1107 order_pos
= ipa_reduced_postorder (order
, true, false, NULL
);
1110 dump_cgraph (dump_file
);
1111 ipa_print_order(dump_file
, "reduced", order
, order_pos
);
1114 /* Propagate the local information through the call graph to produce
1115 the global information. All the nodes within a cycle will have
1116 the same info so we collapse cycles first. Then we can do the
1117 propagation in one pass from the leaves to the roots. */
1118 for (i
= 0; i
< order_pos
; i
++ )
1120 enum pure_const_state_e pure_const_state
= IPA_CONST
;
1121 bool looping
= false;
1128 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1129 fprintf (dump_file
, "Starting cycle\n");
1131 /* Find the worst state for any node in the cycle. */
1133 while (w
&& pure_const_state
!= IPA_NEITHER
)
1135 struct cgraph_edge
*e
;
1136 struct cgraph_edge
*ie
;
1138 struct ipa_ref
*ref
;
1140 funct_state w_l
= get_function_state (w
);
1141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1142 fprintf (dump_file
, " Visiting %s/%i state:%s looping %i\n",
1143 cgraph_node_name (w
),
1145 pure_const_names
[w_l
->pure_const_state
],
1148 /* First merge in function body properties. */
1149 worse_state (&pure_const_state
, &looping
,
1150 w_l
->pure_const_state
, w_l
->looping
);
1151 if (pure_const_state
== IPA_NEITHER
)
1154 /* For overwritable nodes we can not assume anything. */
1155 if (cgraph_function_body_availability (w
) == AVAIL_OVERWRITABLE
)
1157 worse_state (&pure_const_state
, &looping
,
1158 w_l
->state_previously_known
,
1159 w_l
->looping_previously_known
);
1160 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1163 " Overwritable. state %s looping %i\n",
1164 pure_const_names
[w_l
->state_previously_known
],
1165 w_l
->looping_previously_known
);
1172 /* We consider recursive cycles as possibly infinite.
1173 This might be relaxed since infinite recursion leads to stack
1178 /* Now walk the edges and merge in callee properties. */
1179 for (e
= w
->callees
; e
; e
= e
->next_callee
)
1181 enum availability avail
;
1182 struct cgraph_node
*y
= cgraph_function_node (e
->callee
, &avail
);
1183 enum pure_const_state_e edge_state
= IPA_CONST
;
1184 bool edge_looping
= false;
1186 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1190 cgraph_node_name (e
->callee
),
1193 if (avail
> AVAIL_OVERWRITABLE
)
1195 funct_state y_l
= get_function_state (y
);
1196 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1199 " state:%s looping:%i\n",
1200 pure_const_names
[y_l
->pure_const_state
],
1203 if (y_l
->pure_const_state
> IPA_PURE
1204 && cgraph_edge_cannot_lead_to_return (e
))
1206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1208 " Ignoring side effects"
1209 " -> pure, looping\n");
1210 edge_state
= IPA_PURE
;
1211 edge_looping
= true;
1215 edge_state
= y_l
->pure_const_state
;
1216 edge_looping
= y_l
->looping
;
1219 else if (special_builtin_state (&edge_state
, &edge_looping
,
1223 state_from_flags (&edge_state
, &edge_looping
,
1224 flags_from_decl_or_type (y
->symbol
.decl
),
1225 cgraph_edge_cannot_lead_to_return (e
));
1227 /* Merge the results with what we already know. */
1228 better_state (&edge_state
, &edge_looping
,
1229 w_l
->state_previously_known
,
1230 w_l
->looping_previously_known
);
1231 worse_state (&pure_const_state
, &looping
,
1232 edge_state
, edge_looping
);
1233 if (pure_const_state
== IPA_NEITHER
)
1236 if (pure_const_state
== IPA_NEITHER
)
1239 /* Now process the indirect call. */
1240 for (ie
= w
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1242 enum pure_const_state_e edge_state
= IPA_CONST
;
1243 bool edge_looping
= false;
1245 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1246 fprintf (dump_file
, " Indirect call");
1247 state_from_flags (&edge_state
, &edge_looping
,
1248 ie
->indirect_info
->ecf_flags
,
1249 cgraph_edge_cannot_lead_to_return (ie
));
1250 /* Merge the results with what we already know. */
1251 better_state (&edge_state
, &edge_looping
,
1252 w_l
->state_previously_known
,
1253 w_l
->looping_previously_known
);
1254 worse_state (&pure_const_state
, &looping
,
1255 edge_state
, edge_looping
);
1256 if (pure_const_state
== IPA_NEITHER
)
1259 if (pure_const_state
== IPA_NEITHER
)
1262 /* And finally all loads and stores. */
1263 for (i
= 0; ipa_ref_list_reference_iterate (&w
->symbol
.ref_list
, i
, ref
); i
++)
1265 enum pure_const_state_e ref_state
= IPA_CONST
;
1266 bool ref_looping
= false;
1270 /* readonly reads are safe. */
1271 if (TREE_READONLY (ipa_ref_varpool_node (ref
)->symbol
.decl
))
1273 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1274 fprintf (dump_file
, " nonreadonly global var read\n");
1275 ref_state
= IPA_PURE
;
1278 if (ipa_ref_cannot_lead_to_return (ref
))
1280 ref_state
= IPA_NEITHER
;
1281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1282 fprintf (dump_file
, " global var write\n");
1287 better_state (&ref_state
, &ref_looping
,
1288 w_l
->state_previously_known
,
1289 w_l
->looping_previously_known
);
1290 worse_state (&pure_const_state
, &looping
,
1291 ref_state
, ref_looping
);
1292 if (pure_const_state
== IPA_NEITHER
)
1295 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1296 w
= w_info
->next_cycle
;
1298 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1299 fprintf (dump_file
, "Result %s looping %i\n",
1300 pure_const_names
[pure_const_state
],
1303 /* Copy back the region's pure_const_state which is shared by
1304 all nodes in the region. */
1308 funct_state w_l
= get_function_state (w
);
1309 enum pure_const_state_e this_state
= pure_const_state
;
1310 bool this_looping
= looping
;
1312 if (w_l
->state_previously_known
!= IPA_NEITHER
1313 && this_state
> w_l
->state_previously_known
)
1315 this_state
= w_l
->state_previously_known
;
1316 this_looping
|= w_l
->looping_previously_known
;
1318 if (!this_looping
&& self_recursive_p (w
))
1319 this_looping
= true;
1320 if (!w_l
->looping_previously_known
)
1321 this_looping
= false;
1323 /* All nodes within a cycle share the same info. */
1324 w_l
->pure_const_state
= this_state
;
1325 w_l
->looping
= this_looping
;
1330 if (!TREE_READONLY (w
->symbol
.decl
))
1332 warn_function_const (w
->symbol
.decl
, !this_looping
);
1334 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1335 this_looping
? "looping " : "",
1336 cgraph_node_name (w
));
1338 cgraph_set_const_flag (w
, true, this_looping
);
1342 if (!DECL_PURE_P (w
->symbol
.decl
))
1344 warn_function_pure (w
->symbol
.decl
, !this_looping
);
1346 fprintf (dump_file
, "Function found to be %spure: %s\n",
1347 this_looping
? "looping " : "",
1348 cgraph_node_name (w
));
1350 cgraph_set_pure_flag (w
, true, this_looping
);
1356 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1357 w
= w_info
->next_cycle
;
1361 ipa_free_postorder_info ();
1365 /* Produce transitive closure over the callgraph and compute nothrow
1369 propagate_nothrow (void)
1371 struct cgraph_node
*node
;
1372 struct cgraph_node
*w
;
1373 struct cgraph_node
**order
=
1374 XCNEWVEC (struct cgraph_node
*, cgraph_n_nodes
);
1377 struct ipa_dfs_info
* w_info
;
1379 order_pos
= ipa_reduced_postorder (order
, true, false, ignore_edge
);
1382 dump_cgraph (dump_file
);
1383 ipa_print_order (dump_file
, "reduced for nothrow", order
, order_pos
);
1386 /* Propagate the local information through the call graph to produce
1387 the global information. All the nodes within a cycle will have
1388 the same info so we collapse cycles first. Then we can do the
1389 propagation in one pass from the leaves to the roots. */
1390 for (i
= 0; i
< order_pos
; i
++ )
1392 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 enum availability avail
;
1415 struct cgraph_node
*y
= cgraph_function_node (e
->callee
, &avail
);
1417 if (avail
> AVAIL_OVERWRITABLE
)
1419 funct_state y_l
= get_function_state (y
);
1423 if (y_l
->can_throw
&& !TREE_NOTHROW (w
->symbol
.decl
)
1424 && e
->can_throw_external
)
1427 else if (e
->can_throw_external
&& !TREE_NOTHROW (y
->symbol
.decl
))
1430 for (ie
= node
->indirect_calls
; ie
; ie
= ie
->next_callee
)
1431 if (ie
->can_throw_external
)
1433 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1434 w
= w_info
->next_cycle
;
1437 /* Copy back the region's pure_const_state which is shared by
1438 all nodes in the region. */
1442 funct_state w_l
= get_function_state (w
);
1443 if (!can_throw
&& !TREE_NOTHROW (w
->symbol
.decl
))
1445 cgraph_set_nothrow_flag (w
, true);
1447 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1448 cgraph_node_name (w
));
1450 else if (can_throw
&& !TREE_NOTHROW (w
->symbol
.decl
))
1451 w_l
->can_throw
= true;
1452 w_info
= (struct ipa_dfs_info
*) w
->symbol
.aux
;
1453 w
= w_info
->next_cycle
;
1457 ipa_free_postorder_info ();
1462 /* Produce the global information by preforming a transitive closure
1463 on the local information that was produced by generate_summary. */
1468 struct cgraph_node
*node
;
1470 cgraph_remove_function_insertion_hook (function_insertion_hook_holder
);
1471 cgraph_remove_node_duplication_hook (node_duplication_hook_holder
);
1472 cgraph_remove_node_removal_hook (node_removal_hook_holder
);
1474 /* Nothrow makes more function to not lead to return and improve
1476 propagate_nothrow ();
1477 propagate_pure_const ();
1480 FOR_EACH_DEFINED_FUNCTION (node
)
1481 if (has_function_state (node
))
1482 free (get_function_state (node
));
1483 funct_state_vec
.release ();
1489 gate_pure_const (void)
1491 return (flag_ipa_pure_const
1492 /* Don't bother doing anything if the program has errors. */
1496 struct ipa_opt_pass_d pass_ipa_pure_const
=
1500 "pure-const", /* name */
1501 OPTGROUP_NONE
, /* optinfo_flags */
1502 gate_pure_const
, /* gate */
1503 propagate
, /* execute */
1506 0, /* static_pass_number */
1507 TV_IPA_PURE_CONST
, /* tv_id */
1508 0, /* properties_required */
1509 0, /* properties_provided */
1510 0, /* properties_destroyed */
1511 0, /* todo_flags_start */
1512 0 /* todo_flags_finish */
1514 generate_summary
, /* generate_summary */
1515 pure_const_write_summary
, /* write_summary */
1516 pure_const_read_summary
, /* read_summary */
1517 NULL
, /* write_optimization_summary */
1518 NULL
, /* read_optimization_summary */
1519 NULL
, /* stmt_fixup */
1521 NULL
, /* function_transform */
1522 NULL
/* variable_transform */
1525 /* Return true if function should be skipped for local pure const analysis. */
1528 skip_function_for_local_pure_const (struct cgraph_node
*node
)
1530 /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1531 we must not promote functions that are called by already processed functions. */
1533 if (function_called_by_processed_nodes_p ())
1536 fprintf (dump_file
, "Function called in recursive cycle; ignoring\n");
1539 if (cgraph_function_body_availability (node
) <= AVAIL_OVERWRITABLE
)
1542 fprintf (dump_file
, "Function is not available or overwritable; not analyzing.\n");
1548 /* Simple local pass for pure const discovery reusing the analysis from
1549 ipa_pure_const. This pass is effective when executed together with
1550 other optimization passes in early optimization pass queue. */
1553 local_pure_const (void)
1555 bool changed
= false;
1558 struct cgraph_node
*node
;
1560 node
= cgraph_get_node (current_function_decl
);
1561 skip
= skip_function_for_local_pure_const (node
);
1562 if (!warn_suggest_attribute_const
1563 && !warn_suggest_attribute_pure
1567 l
= analyze_function (node
, false);
1569 /* Do NORETURN discovery. */
1570 if (!skip
&& !TREE_THIS_VOLATILE (current_function_decl
)
1571 && EDGE_COUNT (EXIT_BLOCK_PTR
->preds
) == 0)
1573 warn_function_noreturn (cfun
->decl
);
1575 fprintf (dump_file
, "Function found to be noreturn: %s\n",
1576 current_function_name ());
1578 /* Update declaration and reduce profile to executed once. */
1579 TREE_THIS_VOLATILE (current_function_decl
) = 1;
1580 if (node
->frequency
> NODE_FREQUENCY_EXECUTED_ONCE
)
1581 node
->frequency
= NODE_FREQUENCY_EXECUTED_ONCE
;
1586 switch (l
->pure_const_state
)
1589 if (!TREE_READONLY (current_function_decl
))
1591 warn_function_const (current_function_decl
, !l
->looping
);
1594 cgraph_set_const_flag (node
, true, l
->looping
);
1598 fprintf (dump_file
, "Function found to be %sconst: %s\n",
1599 l
->looping
? "looping " : "",
1600 current_function_name ());
1602 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1607 cgraph_set_const_flag (node
, true, false);
1611 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1612 current_function_name ());
1617 if (!DECL_PURE_P (current_function_decl
))
1621 cgraph_set_pure_flag (node
, true, l
->looping
);
1624 warn_function_pure (current_function_decl
, !l
->looping
);
1626 fprintf (dump_file
, "Function found to be %spure: %s\n",
1627 l
->looping
? "looping " : "",
1628 current_function_name ());
1630 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl
)
1635 cgraph_set_pure_flag (node
, true, false);
1639 fprintf (dump_file
, "Function found to be non-looping: %s\n",
1640 current_function_name ());
1647 if (!l
->can_throw
&& !TREE_NOTHROW (current_function_decl
))
1649 cgraph_set_nothrow_flag (node
, true);
1652 fprintf (dump_file
, "Function found to be nothrow: %s\n",
1653 current_function_name ());
1657 return execute_fixup_cfg ();
1662 struct gimple_opt_pass pass_local_pure_const
=
1666 "local-pure-const", /* name */
1667 OPTGROUP_NONE
, /* optinfo_flags */
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 */