1 /* Callgraph based analysis of static variables.
2 Copyright (C) 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file marks functions as being either const (TREE_READONLY) or
23 pure (DECL_PURE_P). It can also set a variant of these that
24 are allowed to loop indefinitely (DECL_LOOPING_CONST_PURE_P).
26 This must be run after inlining decisions have been made since
27 otherwise, the local sets will not contain information that is
28 consistent with post inlined state. The global sets are not prone
29 to this problem since they are by definition transitive. */
31 /* The code in this module is called by the ipa pass manager. It
32 should be one of the later passes since it's information is used by
33 the rest of the compilation. */
37 #include "coretypes.h"
40 #include "tree-flow.h"
41 #include "tree-inline.h"
42 #include "tree-pass.h"
43 #include "langhooks.h"
44 #include "pointer-set.h"
46 #include "ipa-utils.h"
53 #include "diagnostic.h"
54 #include "gimple-pretty-print.h"
55 #include "langhooks.h"
57 #include "lto-streamer.h"
59 #include "tree-scalar-evolution.h"
63 static struct pointer_set_t *visited_nodes;
65 /* Lattice values for const and pure functions. Everything starts out
66 being const, then may drop to pure and then neither depending on
68 enum pure_const_state_e
75 const char *pure_const_names[3] = {"const", "pure", "neither"};
77 /* Holder for the const_state. There is one of these per function
82 enum pure_const_state_e pure_const_state;
83 /* What user set here; we can be always sure about this. */
84 enum pure_const_state_e state_previously_known;
85 bool looping_previously_known;
87 /* True if the function could possibly infinite loop. There are a
88 lot of ways that this could be determined. We are pretty
89 conservative here. While it is possible to cse pure and const
90 calls, it is not legal to have dce get rid of the call if there
91 is a possibility that the call could infinite loop since this is
92 a behavioral change. */
98 typedef struct funct_state_d * funct_state;
100 /* The storage of the funct_state is abstracted because there is the
101 possibility that it may be desirable to move this to the cgraph
104 /* Array, indexed by cgraph node uid, of function states. */
106 DEF_VEC_P (funct_state);
107 DEF_VEC_ALLOC_P (funct_state, heap);
108 static VEC (funct_state, heap) *funct_state_vec;
110 /* Holders of ipa cgraph hooks: */
111 static struct cgraph_node_hook_list *function_insertion_hook_holder;
112 static struct cgraph_2node_hook_list *node_duplication_hook_holder;
113 static struct cgraph_node_hook_list *node_removal_hook_holder;
115 /* Try to guess if function body will always be visible to compiler
116 when compiling the call and whether compiler will be able
117 to propagate the information by itself. */
120 function_always_visible_to_compiler_p (tree decl)
122 return (!TREE_PUBLIC (decl) || DECL_DECLARED_INLINE_P (decl));
125 /* Emit suggestion about attribute ATTRIB_NAME for DECL. KNOWN_FINITE
126 is true if the function is known to be finite. The diagnostic is
127 controlled by OPTION. WARNED_ABOUT is a pointer_set unique for
128 OPTION, this function may initialize it and it is always returned
131 static struct pointer_set_t *
132 suggest_attribute (int option, tree decl, bool known_finite,
133 struct pointer_set_t *warned_about,
134 const char * attrib_name)
136 if (!option_enabled (option))
138 if (TREE_THIS_VOLATILE (decl)
139 || (known_finite && function_always_visible_to_compiler_p (decl)))
143 warned_about = pointer_set_create ();
144 if (pointer_set_contains (warned_about, decl))
146 pointer_set_insert (warned_about, decl);
147 warning_at (DECL_SOURCE_LOCATION (decl),
150 ? _("function might be candidate for attribute %<%s%>")
151 : _("function might be candidate for attribute %<%s%>"
152 " if it is known to return normally"), attrib_name);
156 /* Emit suggestion about __attribute_((pure)) for DECL. KNOWN_FINITE
157 is true if the function is known to be finite. */
160 warn_function_pure (tree decl, bool known_finite)
162 static struct pointer_set_t *warned_about;
165 = suggest_attribute (OPT_Wsuggest_attribute_pure, decl,
166 known_finite, warned_about, "pure");
169 /* Emit suggestion about __attribute_((const)) for DECL. KNOWN_FINITE
170 is true if the function is known to be finite. */
173 warn_function_const (tree decl, bool known_finite)
175 static struct pointer_set_t *warned_about;
177 = suggest_attribute (OPT_Wsuggest_attribute_const, decl,
178 known_finite, warned_about, "const");
180 /* Init the function state. */
185 free (funct_state_vec);
189 /* Return the function state from NODE. */
191 static inline funct_state
192 get_function_state (struct cgraph_node *node)
195 || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
197 return VEC_index (funct_state, funct_state_vec, node->uid);
200 /* Set the function state S for NODE. */
203 set_function_state (struct cgraph_node *node, funct_state s)
206 || VEC_length (funct_state, funct_state_vec) <= (unsigned int)node->uid)
207 VEC_safe_grow_cleared (funct_state, heap, funct_state_vec, node->uid + 1);
208 VEC_replace (funct_state, funct_state_vec, node->uid, s);
211 /* Check to see if the use (or definition when CHECKING_WRITE is true)
212 variable T is legal in a function that is either pure or const. */
215 check_decl (funct_state local,
216 tree t, bool checking_write)
218 /* Do not want to do anything with volatile except mark any
219 function that uses one to be not const or pure. */
220 if (TREE_THIS_VOLATILE (t))
222 local->pure_const_state = IPA_NEITHER;
224 fprintf (dump_file, " Volatile operand is not const/pure");
228 /* Do not care about a local automatic that is not static. */
229 if (!TREE_STATIC (t) && !DECL_EXTERNAL (t))
232 /* If the variable has the "used" attribute, treat it as if it had a
233 been touched by the devil. */
234 if (DECL_PRESERVE_P (t))
236 local->pure_const_state = IPA_NEITHER;
238 fprintf (dump_file, " Used static/global variable is not const/pure\n");
242 /* Since we have dealt with the locals and params cases above, if we
243 are CHECKING_WRITE, this cannot be a pure or constant
247 local->pure_const_state = IPA_NEITHER;
249 fprintf (dump_file, " static/global memory write is not const/pure\n");
253 if (DECL_EXTERNAL (t) || TREE_PUBLIC (t))
255 /* Readonly reads are safe. */
256 if (TREE_READONLY (t) && !TYPE_NEEDS_CONSTRUCTING (TREE_TYPE (t)))
257 return; /* Read of a constant, do not change the function state. */
261 fprintf (dump_file, " global memory read is not const\n");
262 /* Just a regular read. */
263 if (local->pure_const_state == IPA_CONST)
264 local->pure_const_state = IPA_PURE;
269 /* Compilation level statics can be read if they are readonly
271 if (TREE_READONLY (t))
275 fprintf (dump_file, " static memory read is not const\n");
276 /* Just a regular read. */
277 if (local->pure_const_state == IPA_CONST)
278 local->pure_const_state = IPA_PURE;
283 /* Check to see if the use (or definition when CHECKING_WRITE is true)
284 variable T is legal in a function that is either pure or const. */
287 check_op (funct_state local, tree t, bool checking_write)
289 t = get_base_address (t);
290 if (t && TREE_THIS_VOLATILE (t))
292 local->pure_const_state = IPA_NEITHER;
294 fprintf (dump_file, " Volatile indirect ref is not const/pure\n");
298 && INDIRECT_REF_P (t)
299 && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
300 && !ptr_deref_may_alias_global_p (TREE_OPERAND (t, 0)))
303 fprintf (dump_file, " Indirect ref to local memory is OK\n");
306 else if (checking_write)
308 local->pure_const_state = IPA_NEITHER;
310 fprintf (dump_file, " Indirect ref write is not const/pure\n");
316 fprintf (dump_file, " Indirect ref read is not const\n");
317 if (local->pure_const_state == IPA_CONST)
318 local->pure_const_state = IPA_PURE;
322 /* Check the parameters of a function call to CALL_EXPR to see if
323 there are any references in the parameters that are not allowed for
324 pure or const functions. Also check to see if this is either an
325 indirect call, a call outside the compilation unit, or has special
326 attributes that may also effect the purity. The CALL_EXPR node for
327 the entire call expression. */
330 check_call (funct_state local, gimple call, bool ipa)
332 int flags = gimple_call_flags (call);
333 tree callee_t = gimple_call_fndecl (call);
334 bool possibly_throws = stmt_could_throw_p (call);
335 bool possibly_throws_externally = (possibly_throws
336 && stmt_can_throw_external (call));
341 for (i = 0; i < gimple_num_ops (call); i++)
342 if (gimple_op (call, i)
343 && tree_could_throw_p (gimple_op (call, i)))
345 if (possibly_throws && cfun->can_throw_non_call_exceptions)
348 fprintf (dump_file, " operand can throw; looping\n");
349 local->looping = true;
351 if (possibly_throws_externally)
354 fprintf (dump_file, " operand can throw externally\n");
355 local->can_throw = true;
360 /* The const and pure flags are set by a variety of places in the
361 compiler (including here). If someone has already set the flags
362 for the callee, (such as for some of the builtins) we will use
363 them, otherwise we will compute our own information.
365 Const and pure functions have less clobber effects than other
366 functions so we process these first. Otherwise if it is a call
367 outside the compilation unit or an indirect call we punt. This
368 leaves local calls which will be processed by following the call
372 /* When bad things happen to bad functions, they cannot be const
374 if (setjmp_call_p (callee_t))
377 fprintf (dump_file, " setjmp is not const/pure\n");
378 local->looping = true;
379 local->pure_const_state = IPA_NEITHER;
382 if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL)
383 switch (DECL_FUNCTION_CODE (callee_t))
385 case BUILT_IN_LONGJMP:
386 case BUILT_IN_NONLOCAL_GOTO:
388 fprintf (dump_file, " longjmp and nonlocal goto is not const/pure\n");
389 local->pure_const_state = IPA_NEITHER;
390 local->looping = true;
397 /* When not in IPA mode, we can still handle self recursion. */
398 if (!ipa && callee_t == current_function_decl)
401 fprintf (dump_file, " Recursive call can loop.\n");
402 local->looping = true;
404 /* Either calle is unknown or we are doing local analysis.
405 Look to see if there are any bits available for the callee (such as by
406 declaration or because it is builtin) and process solely on the basis of
408 else if (!ipa || !callee_t)
410 if (possibly_throws && cfun->can_throw_non_call_exceptions)
413 fprintf (dump_file, " can throw; looping\n");
414 local->looping = true;
416 if (possibly_throws_externally)
420 fprintf (dump_file, " can throw externally to lp %i\n",
421 lookup_stmt_eh_lp (call));
423 fprintf (dump_file, " callee:%s\n",
424 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t)));
426 local->can_throw = true;
428 if (flags & ECF_CONST)
430 if (callee_t && DECL_LOOPING_CONST_OR_PURE_P (callee_t))
433 fprintf (dump_file, " calls looping pure.\n");
434 local->looping = true;
437 else if (flags & ECF_PURE)
439 if (callee_t && DECL_LOOPING_CONST_OR_PURE_P (callee_t))
442 fprintf (dump_file, " calls looping const.\n");
443 local->looping = true;
446 fprintf (dump_file, " pure function call in not const\n");
447 if (local->pure_const_state == IPA_CONST)
448 local->pure_const_state = IPA_PURE;
450 else if ((flags & (ECF_NORETURN | ECF_NOTHROW))
451 == (ECF_NORETURN | ECF_NOTHROW)
452 || (!flag_exceptions && (flags & ECF_NORETURN)))
455 fprintf (dump_file, " noreturn nothrow call is looping pure\n");
456 if (local->pure_const_state == IPA_CONST)
457 local->pure_const_state = IPA_PURE;
458 local->looping = true;
463 fprintf (dump_file, " uknown function call is not const/pure\n");
464 local->pure_const_state = IPA_NEITHER;
465 local->looping = true;
468 /* Direct functions calls are handled by IPA propagation. */
471 /* Wrapper around check_decl for loads. */
474 check_load (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
477 check_decl ((funct_state)data, op, false);
479 check_op ((funct_state)data, op, false);
483 /* Wrapper around check_decl for stores. */
486 check_store (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
489 check_decl ((funct_state)data, op, true);
491 check_op ((funct_state)data, op, true);
495 /* Look into pointer pointed to by GSIP and figure out what interesting side
498 check_stmt (gimple_stmt_iterator *gsip, funct_state local, bool ipa)
500 gimple stmt = gsi_stmt (*gsip);
503 if (is_gimple_debug (stmt))
508 fprintf (dump_file, " scanning: ");
509 print_gimple_stmt (dump_file, stmt, 0, 0);
512 /* Look for loads and stores. */
513 walk_stmt_load_store_ops (stmt, local, check_load, check_store);
515 if (gimple_code (stmt) != GIMPLE_CALL
516 && stmt_could_throw_p (stmt))
518 if (cfun->can_throw_non_call_exceptions)
521 fprintf (dump_file, " can throw; looping");
522 local->looping = true;
524 if (stmt_can_throw_external (stmt))
527 fprintf (dump_file, " can throw externally");
528 local->can_throw = true;
531 switch (gimple_code (stmt))
534 check_call (local, stmt, ipa);
537 if (DECL_NONLOCAL (gimple_label_label (stmt)))
538 /* Target of long jump. */
541 fprintf (dump_file, " nonlocal label is not const/pure");
542 local->pure_const_state = IPA_NEITHER;
546 for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
548 tree op = gimple_asm_clobber_op (stmt, i);
549 if (strcmp (TREE_STRING_POINTER (TREE_VALUE (op)), "memory") == 0)
552 fprintf (dump_file, " memory asm clobber is not const/pure");
553 /* Abandon all hope, ye who enter here. */
554 local->pure_const_state = IPA_NEITHER;
557 if (gimple_asm_volatile_p (stmt))
560 fprintf (dump_file, " volatile is not const/pure");
561 /* Abandon all hope, ye who enter here. */
562 local->pure_const_state = IPA_NEITHER;
563 local->looping = true;
572 /* This is the main routine for finding the reference patterns for
573 global variables within a function FN. */
576 analyze_function (struct cgraph_node *fn, bool ipa)
578 tree decl = fn->decl;
579 tree old_decl = current_function_decl;
581 basic_block this_block;
583 l = XCNEW (struct funct_state_d);
584 l->pure_const_state = IPA_CONST;
585 l->state_previously_known = IPA_NEITHER;
586 l->looping_previously_known = true;
588 l->can_throw = false;
592 fprintf (dump_file, "\n\n local analysis of %s\n ",
593 cgraph_node_name (fn));
596 push_cfun (DECL_STRUCT_FUNCTION (decl));
597 current_function_decl = decl;
599 FOR_EACH_BB (this_block)
601 gimple_stmt_iterator gsi;
602 struct walk_stmt_info wi;
604 memset (&wi, 0, sizeof(wi));
605 for (gsi = gsi_start_bb (this_block);
609 check_stmt (&gsi, l, ipa);
610 if (l->pure_const_state == IPA_NEITHER && l->looping && l->can_throw)
616 if (l->pure_const_state != IPA_NEITHER)
618 /* Const functions cannot have back edges (an
619 indication of possible infinite loop side
621 if (mark_dfs_back_edges ())
623 /* Preheaders are needed for SCEV to work.
624 Simple lateches and recorded exits improve chances that loop will
625 proved to be finite in testcases such as in loop-15.c and loop-24.c */
626 loop_optimizer_init (LOOPS_NORMAL
627 | LOOPS_HAVE_RECORDED_EXITS);
628 if (dump_file && (dump_flags & TDF_DETAILS))
629 flow_loops_dump (dump_file, NULL, 0);
630 if (mark_irreducible_loops ())
633 fprintf (dump_file, " has irreducible loops\n");
641 FOR_EACH_LOOP (li, loop, 0)
642 if (!finite_loop_p (loop))
645 fprintf (dump_file, " can not prove finiteness of loop %i\n", loop->num);
651 loop_optimizer_finalize ();
655 if (TREE_READONLY (decl))
657 l->pure_const_state = IPA_CONST;
658 l->state_previously_known = IPA_CONST;
659 if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
660 l->looping = false, l->looping_previously_known = false;
662 if (DECL_PURE_P (decl))
664 if (l->pure_const_state != IPA_CONST)
665 l->pure_const_state = IPA_PURE;
666 l->state_previously_known = IPA_PURE;
667 if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
668 l->looping = false, l->looping_previously_known = false;
670 if (TREE_NOTHROW (decl))
671 l->can_throw = false;
674 current_function_decl = old_decl;
678 fprintf (dump_file, "Function is locally looping.\n");
680 fprintf (dump_file, "Function is locally throwing.\n");
681 if (l->pure_const_state == IPA_CONST)
682 fprintf (dump_file, "Function is locally const.\n");
683 if (l->pure_const_state == IPA_PURE)
684 fprintf (dump_file, "Function is locally pure.\n");
689 /* Called when new function is inserted to callgraph late. */
691 add_new_function (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
693 if (cgraph_function_body_availability (node) < AVAIL_OVERWRITABLE)
695 /* There are some shared nodes, in particular the initializers on
696 static declarations. We do not need to scan them more than once
697 since all we would be interested in are the addressof
699 visited_nodes = pointer_set_create ();
700 if (cgraph_function_body_availability (node) > AVAIL_OVERWRITABLE)
701 set_function_state (node, analyze_function (node, true));
702 pointer_set_destroy (visited_nodes);
703 visited_nodes = NULL;
706 /* Called when new clone is inserted to callgraph late. */
709 duplicate_node_data (struct cgraph_node *src, struct cgraph_node *dst,
710 void *data ATTRIBUTE_UNUSED)
712 if (get_function_state (src))
714 funct_state l = XNEW (struct funct_state_d);
715 gcc_assert (!get_function_state (dst));
716 memcpy (l, get_function_state (src), sizeof (*l));
717 set_function_state (dst, l);
721 /* Called when new clone is inserted to callgraph late. */
724 remove_node_data (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
726 if (get_function_state (node))
728 free (get_function_state (node));
729 set_function_state (node, NULL);
735 register_hooks (void)
737 static bool init_p = false;
744 node_removal_hook_holder =
745 cgraph_add_node_removal_hook (&remove_node_data, NULL);
746 node_duplication_hook_holder =
747 cgraph_add_node_duplication_hook (&duplicate_node_data, NULL);
748 function_insertion_hook_holder =
749 cgraph_add_function_insertion_hook (&add_new_function, NULL);
753 /* Analyze each function in the cgraph to see if it is locally PURE or
757 generate_summary (void)
759 struct cgraph_node *node;
763 /* There are some shared nodes, in particular the initializers on
764 static declarations. We do not need to scan them more than once
765 since all we would be interested in are the addressof
767 visited_nodes = pointer_set_create ();
769 /* Process all of the functions.
771 We process AVAIL_OVERWRITABLE functions. We can not use the results
772 by default, but the info can be used at LTO with -fwhole-program or
773 when function got clonned and the clone is AVAILABLE. */
775 for (node = cgraph_nodes; node; node = node->next)
776 if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
777 set_function_state (node, analyze_function (node, true));
779 pointer_set_destroy (visited_nodes);
780 visited_nodes = NULL;
784 /* Serialize the ipa info for lto. */
787 pure_const_write_summary (cgraph_node_set set,
788 varpool_node_set vset ATTRIBUTE_UNUSED)
790 struct cgraph_node *node;
791 struct lto_simple_output_block *ob
792 = lto_create_simple_output_block (LTO_section_ipa_pure_const);
793 unsigned int count = 0;
794 cgraph_node_set_iterator csi;
796 for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
798 node = csi_node (csi);
799 if (node->analyzed && get_function_state (node) != NULL)
803 lto_output_uleb128_stream (ob->main_stream, count);
805 /* Process all of the functions. */
806 for (csi = csi_start (set); !csi_end_p (csi); csi_next (&csi))
808 node = csi_node (csi);
809 if (node->analyzed && get_function_state (node) != NULL)
811 struct bitpack_d *bp;
814 lto_cgraph_encoder_t encoder;
816 fs = get_function_state (node);
818 encoder = ob->decl_state->cgraph_node_encoder;
819 node_ref = lto_cgraph_encoder_encode (encoder, node);
820 lto_output_uleb128_stream (ob->main_stream, node_ref);
822 /* Note that flags will need to be read in the opposite
823 order as we are pushing the bitflags into FLAGS. */
824 bp = bitpack_create ();
825 bp_pack_value (bp, fs->pure_const_state, 2);
826 bp_pack_value (bp, fs->state_previously_known, 2);
827 bp_pack_value (bp, fs->looping_previously_known, 1);
828 bp_pack_value (bp, fs->looping, 1);
829 bp_pack_value (bp, fs->can_throw, 1);
830 lto_output_bitpack (ob->main_stream, bp);
835 lto_destroy_simple_output_block (ob);
839 /* Deserialize the ipa info for lto. */
842 pure_const_read_summary (void)
844 struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data ();
845 struct lto_file_decl_data *file_data;
849 while ((file_data = file_data_vec[j++]))
853 struct lto_input_block *ib
854 = lto_create_simple_input_block (file_data,
855 LTO_section_ipa_pure_const,
860 unsigned int count = lto_input_uleb128 (ib);
862 for (i = 0; i < count; i++)
865 struct cgraph_node *node;
866 struct bitpack_d *bp;
868 lto_cgraph_encoder_t encoder;
870 fs = XCNEW (struct funct_state_d);
871 index = lto_input_uleb128 (ib);
872 encoder = file_data->cgraph_node_encoder;
873 node = lto_cgraph_encoder_deref (encoder, index);
874 set_function_state (node, fs);
876 /* Note that the flags must be read in the opposite
877 order in which they were written (the bitflags were
878 pushed into FLAGS). */
879 bp = lto_input_bitpack (ib);
881 = (enum pure_const_state_e) bp_unpack_value (bp, 2);
882 fs->state_previously_known
883 = (enum pure_const_state_e) bp_unpack_value (bp, 2);
884 fs->looping_previously_known = bp_unpack_value (bp, 1);
885 fs->looping = bp_unpack_value (bp, 1);
886 fs->can_throw = bp_unpack_value (bp, 1);
889 int flags = flags_from_decl_or_type (node->decl);
890 fprintf (dump_file, "Read info for %s/%i ",
891 cgraph_node_name (node),
893 if (flags & ECF_CONST)
894 fprintf (dump_file, " const");
895 if (flags & ECF_PURE)
896 fprintf (dump_file, " pure");
897 if (flags & ECF_NOTHROW)
898 fprintf (dump_file, " nothrow");
899 fprintf (dump_file, "\n pure const state: %s\n",
900 pure_const_names[fs->pure_const_state]);
901 fprintf (dump_file, " previously known state: %s\n",
902 pure_const_names[fs->looping_previously_known]);
904 fprintf (dump_file," function is locally looping\n");
905 if (fs->looping_previously_known)
906 fprintf (dump_file," function is previously known looping\n");
908 fprintf (dump_file," function is locally throwing\n");
913 lto_destroy_simple_input_block (file_data,
914 LTO_section_ipa_pure_const,
922 ignore_edge (struct cgraph_edge *e)
924 return (!e->can_throw_external);
927 /* Return true if NODE is self recursive function. */
930 self_recursive_p (struct cgraph_node *node)
932 struct cgraph_edge *e;
933 for (e = node->callees; e; e = e->next_callee)
934 if (e->callee == node)
939 /* Produce the global information by preforming a transitive closure
940 on the local information that was produced by generate_summary.
941 Note that there is no function_transform pass since this only
942 updates the function_decl. */
947 struct cgraph_node *node;
948 struct cgraph_node *w;
949 struct cgraph_node **order =
950 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
953 struct ipa_dfs_info * w_info;
955 cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
956 cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
957 cgraph_remove_node_removal_hook (node_removal_hook_holder);
958 order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
961 dump_cgraph (dump_file);
962 ipa_utils_print_order(dump_file, "reduced", order, order_pos);
965 /* Propagate the local information thru the call graph to produce
966 the global information. All the nodes within a cycle will have
967 the same info so we collapse cycles first. Then we can do the
968 propagation in one pass from the leaves to the roots. */
969 for (i = 0; i < order_pos; i++ )
971 enum pure_const_state_e pure_const_state = IPA_CONST;
972 bool looping = false;
976 if (dump_file && (dump_flags & TDF_DETAILS))
977 fprintf (dump_file, "Starting cycle\n");
979 /* Find the worst state for any node in the cycle. */
983 struct cgraph_edge *e;
984 funct_state w_l = get_function_state (w);
985 if (dump_file && (dump_flags & TDF_DETAILS))
986 fprintf (dump_file, " Visiting %s/%i state:%s looping %i\n",
987 cgraph_node_name (w),
989 pure_const_names[w_l->pure_const_state],
991 if (pure_const_state < w_l->pure_const_state)
992 pure_const_state = w_l->pure_const_state;
996 if (cgraph_function_body_availability (w) == AVAIL_OVERWRITABLE)
998 looping |= w_l->looping_previously_known;
999 if (pure_const_state < w_l->state_previously_known)
1000 pure_const_state = w_l->state_previously_known;
1001 if (dump_file && (dump_flags & TDF_DETAILS))
1004 " Overwritable. state %s looping %i\n",
1005 pure_const_names[w_l->state_previously_known],
1006 w_l->looping_previously_known);
1010 if (pure_const_state == IPA_NEITHER)
1018 for (e = w->callees; e; e = e->next_callee)
1020 struct cgraph_node *y = e->callee;
1021 enum pure_const_state_e edge_state = IPA_CONST;
1022 bool edge_looping = false;
1024 if (dump_file && (dump_flags & TDF_DETAILS))
1028 cgraph_node_name (e->callee),
1031 if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
1033 funct_state y_l = get_function_state (y);
1034 if (dump_file && (dump_flags & TDF_DETAILS))
1037 " state:%s looping:%i\n",
1038 pure_const_names[y_l->pure_const_state],
1041 else if (y_l->pure_const_state > ECF_PURE
1042 && cgraph_edge_cannot_lead_to_return (e))
1044 if (dump_file && (dump_flags & TDF_DETAILS))
1047 " Ignoring side effects -> pure, looping\n");
1049 edge_state = IPA_PURE;
1050 edge_looping = true;
1054 edge_state = y_l->pure_const_state;
1055 edge_looping = y_l->looping;
1060 int flags = flags_from_decl_or_type (y->decl);
1062 if (flags & ECF_LOOPING_CONST_OR_PURE)
1064 edge_looping = true;
1065 if (dump_file && (dump_flags & TDF_DETAILS))
1066 fprintf (dump_file, " unavailable looping");
1068 if (flags & ECF_CONST)
1070 if (dump_file && (dump_flags & TDF_DETAILS))
1071 fprintf (dump_file, " const\n");
1073 else if (flags & ECF_PURE)
1075 edge_state = IPA_PURE;
1076 if (dump_file && (dump_flags & TDF_DETAILS))
1077 fprintf (dump_file, " pure\n");
1079 else if (cgraph_edge_cannot_lead_to_return (e))
1081 edge_state = IPA_PURE;
1082 edge_looping = true;
1083 if (dump_file && (dump_flags & TDF_DETAILS))
1084 fprintf (dump_file, " ignoring side effects->pure looping\n");
1088 if (dump_file && (dump_flags & TDF_DETAILS))
1089 fprintf (dump_file, " neihter\n");
1090 edge_state = IPA_NEITHER;
1091 edge_looping = true;
1094 pure_const_state = MAX (pure_const_state, MIN (edge_state,
1095 w_l->state_previously_known));
1096 looping = MAX (looping, MIN (edge_looping, edge_state));
1097 if (pure_const_state == IPA_NEITHER)
1100 w_info = (struct ipa_dfs_info *) w->aux;
1101 w = w_info->next_cycle;
1103 if (dump_file && (dump_flags & TDF_DETAILS))
1104 fprintf (dump_file, "Result %s looping %i\n",
1105 pure_const_names [pure_const_state],
1108 /* Copy back the region's pure_const_state which is shared by
1109 all nodes in the region. */
1113 funct_state w_l = get_function_state (w);
1114 enum pure_const_state_e this_state = pure_const_state;
1115 bool this_looping = looping;
1117 if (w_l->state_previously_known != IPA_NEITHER
1118 && this_state > w_l->state_previously_known)
1119 this_state = w_l->state_previously_known;
1120 if (!this_looping && self_recursive_p (w))
1121 this_looping = true;
1122 if (!w_l->looping_previously_known)
1123 this_looping = false;
1125 /* All nodes within a cycle share the same info. */
1126 w_l->pure_const_state = this_state;
1127 w_l->looping = this_looping;
1132 if (!TREE_READONLY (w->decl))
1134 warn_function_const (w->decl, !this_looping);
1136 fprintf (dump_file, "Function found to be %sconst: %s\n",
1137 this_looping ? "looping " : "",
1138 cgraph_node_name (w));
1140 cgraph_set_readonly_flag (w, true);
1141 cgraph_set_looping_const_or_pure_flag (w, this_looping);
1145 if (!DECL_PURE_P (w->decl))
1147 warn_function_pure (w->decl, !this_looping);
1149 fprintf (dump_file, "Function found to be %spure: %s\n",
1150 this_looping ? "looping " : "",
1151 cgraph_node_name (w));
1153 cgraph_set_pure_flag (w, true);
1154 cgraph_set_looping_const_or_pure_flag (w, this_looping);
1160 w_info = (struct ipa_dfs_info *) w->aux;
1161 w = w_info->next_cycle;
1166 for (node = cgraph_nodes; node; node = node->next)
1168 /* Get rid of the aux information. */
1171 w_info = (struct ipa_dfs_info *) node->aux;
1176 order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
1179 dump_cgraph (dump_file);
1180 ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
1182 /* Propagate the local information thru the call graph to produce
1183 the global information. All the nodes within a cycle will have
1184 the same info so we collapse cycles first. Then we can do the
1185 propagation in one pass from the leaves to the roots. */
1186 for (i = 0; i < order_pos; i++ )
1188 bool can_throw = false;
1191 /* Find the worst state for any node in the cycle. */
1195 struct cgraph_edge *e;
1196 funct_state w_l = get_function_state (w);
1199 || cgraph_function_body_availability (w) == AVAIL_OVERWRITABLE)
1205 for (e = w->callees; e; e = e->next_callee)
1207 struct cgraph_node *y = e->callee;
1209 if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
1211 funct_state y_l = get_function_state (y);
1215 if (y_l->can_throw && !TREE_NOTHROW (w->decl)
1216 && e->can_throw_external)
1219 else if (e->can_throw_external && !TREE_NOTHROW (y->decl))
1222 w_info = (struct ipa_dfs_info *) w->aux;
1223 w = w_info->next_cycle;
1226 /* Copy back the region's pure_const_state which is shared by
1227 all nodes in the region. */
1231 funct_state w_l = get_function_state (w);
1232 if (!can_throw && !TREE_NOTHROW (w->decl))
1234 struct cgraph_edge *e;
1235 cgraph_set_nothrow_flag (w, true);
1236 for (e = w->callers; e; e = e->next_caller)
1237 e->can_throw_external = false;
1239 fprintf (dump_file, "Function found to be nothrow: %s\n",
1240 cgraph_node_name (w));
1242 else if (can_throw && !TREE_NOTHROW (w->decl))
1243 w_l->can_throw = true;
1244 w_info = (struct ipa_dfs_info *) w->aux;
1245 w = w_info->next_cycle;
1250 for (node = cgraph_nodes; node; node = node->next)
1252 /* Get rid of the aux information. */
1255 w_info = (struct ipa_dfs_info *) node->aux;
1259 if (cgraph_function_body_availability (node) >= AVAIL_OVERWRITABLE)
1260 free (get_function_state (node));
1264 VEC_free (funct_state, heap, funct_state_vec);
1270 gate_pure_const (void)
1272 return (flag_ipa_pure_const
1273 /* Don't bother doing anything if the program has errors. */
1277 struct ipa_opt_pass_d pass_ipa_pure_const =
1281 "pure-const", /* name */
1282 gate_pure_const, /* gate */
1283 propagate, /* execute */
1286 0, /* static_pass_number */
1287 TV_IPA_PURE_CONST, /* tv_id */
1288 0, /* properties_required */
1289 0, /* properties_provided */
1290 0, /* properties_destroyed */
1291 0, /* todo_flags_start */
1292 0 /* todo_flags_finish */
1294 generate_summary, /* generate_summary */
1295 pure_const_write_summary, /* write_summary */
1296 pure_const_read_summary, /* read_summary */
1297 NULL, /* write_optimization_summary */
1298 NULL, /* read_optimization_summary */
1299 NULL, /* stmt_fixup */
1301 NULL, /* function_transform */
1302 NULL /* variable_transform */
1305 /* Return true if function should be skipped for local pure const analysis. */
1308 skip_function_for_local_pure_const (struct cgraph_node *node)
1310 /* Because we do not schedule pass_fixup_cfg over whole program after early optimizations
1311 we must not promote functions that are called by already processed functions. */
1313 if (function_called_by_processed_nodes_p ())
1316 fprintf (dump_file, "Function called in recursive cycle; ignoring\n");
1319 if (cgraph_function_body_availability (node) <= AVAIL_OVERWRITABLE)
1322 fprintf (dump_file, "Function is not available or overwrittable; not analyzing.\n");
1328 /* Simple local pass for pure const discovery reusing the analysis from
1329 ipa_pure_const. This pass is effective when executed together with
1330 other optimization passes in early optimization pass queue. */
1333 local_pure_const (void)
1335 bool changed = false;
1338 struct cgraph_node *node;
1340 node = cgraph_node (current_function_decl);
1341 skip = skip_function_for_local_pure_const (node);
1342 if (!warn_suggest_attribute_const
1343 && !warn_suggest_attribute_pure
1346 l = analyze_function (node, false);
1348 switch (l->pure_const_state)
1351 if (!TREE_READONLY (current_function_decl))
1353 warn_function_const (current_function_decl, !l->looping);
1356 cgraph_set_readonly_flag (node, true);
1357 cgraph_set_looping_const_or_pure_flag (node, l->looping);
1361 fprintf (dump_file, "Function found to be %sconst: %s\n",
1362 l->looping ? "looping " : "",
1363 lang_hooks.decl_printable_name (current_function_decl,
1366 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1371 cgraph_set_looping_const_or_pure_flag (node, false);
1375 fprintf (dump_file, "Function found to be non-looping: %s\n",
1376 lang_hooks.decl_printable_name (current_function_decl,
1382 if (!DECL_PURE_P (current_function_decl))
1386 cgraph_set_pure_flag (node, true);
1387 cgraph_set_looping_const_or_pure_flag (node, l->looping);
1390 warn_function_pure (current_function_decl, !l->looping);
1392 fprintf (dump_file, "Function found to be %spure: %s\n",
1393 l->looping ? "looping " : "",
1394 lang_hooks.decl_printable_name (current_function_decl,
1397 else if (DECL_LOOPING_CONST_OR_PURE_P (current_function_decl)
1402 cgraph_set_looping_const_or_pure_flag (node, false);
1406 fprintf (dump_file, "Function found to be non-looping: %s\n",
1407 lang_hooks.decl_printable_name (current_function_decl,
1415 if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
1417 struct cgraph_edge *e;
1419 cgraph_set_nothrow_flag (node, true);
1420 for (e = node->callers; e; e = e->next_caller)
1421 e->can_throw_external = false;
1424 fprintf (dump_file, "Function found to be nothrow: %s\n",
1425 lang_hooks.decl_printable_name (current_function_decl,
1431 return execute_fixup_cfg ();
1436 struct gimple_opt_pass pass_local_pure_const =
1440 "local-pure-const", /* name */
1441 gate_pure_const, /* gate */
1442 local_pure_const, /* execute */
1445 0, /* static_pass_number */
1446 TV_IPA_PURE_CONST, /* tv_id */
1447 0, /* properties_required */
1448 0, /* properties_provided */
1449 0, /* properties_destroyed */
1450 0, /* todo_flags_start */
1451 0 /* todo_flags_finish */