/* Callgraph based analysis of static variables.
- Copyright (C) 2004, 2005, 2007, 2008 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2007, 2008, 2009 Free Software Foundation, Inc.
Contributed by Kenneth Zadeck <zadeck@naturalbridge.com>
This file is part of GCC.
#include "pointer-set.h"
#include "ggc.h"
#include "ipa-utils.h"
-#include "c-common.h"
#include "gimple.h"
#include "cgraph.h"
#include "output.h"
#include "diagnostic.h"
#include "langhooks.h"
#include "target.h"
+#include "cfgloop.h"
+#include "tree-scalar-evolution.h"
static struct pointer_set_t *visited_nodes;
/* See above. */
enum pure_const_state_e pure_const_state;
/* What user set here; we can be always sure about this. */
- enum pure_const_state_e state_set_in_source;
+ enum pure_const_state_e state_previously_known;
+ bool looping_previously_known;
/* True if the function could possibly infinite loop. There are a
lot of ways that this could be determined. We are pretty
static inline void
check_op (funct_state local, tree t, bool checking_write)
{
- if (TREE_THIS_VOLATILE (t))
+ t = get_base_address (t);
+ if (t && TREE_THIS_VOLATILE (t))
{
local->pure_const_state = IPA_NEITHER;
if (dump_file)
fprintf (dump_file, " Volatile indirect ref is not const/pure\n");
return;
}
+ else if (t
+ && INDIRECT_REF_P (t)
+ && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME
+ && !ptr_deref_may_alias_global_p (TREE_OPERAND (t, 0)))
+ {
+ if (dump_file)
+ fprintf (dump_file, " Indirect ref to local memory is OK\n");
+ return;
+ }
else if (checking_write)
{
local->pure_const_state = IPA_NEITHER;
{
if (dump_file)
{
- fprintf (dump_file, " can throw externally in region %i\n",
- lookup_stmt_eh_region (call));
+ fprintf (dump_file, " can throw externally to lp %i\n",
+ lookup_stmt_eh_lp (call));
if (callee_t)
fprintf (dump_file, " callee:%s\n",
IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (callee_t)));
gimple stmt = gsi_stmt (*gsip);
unsigned int i = 0;
+ if (is_gimple_debug (stmt))
+ return;
+
if (dump_file)
{
fprintf (dump_file, " scanning: ");
l = XCNEW (struct funct_state_d);
l->pure_const_state = IPA_CONST;
- l->state_set_in_source = IPA_NEITHER;
+ l->state_previously_known = IPA_NEITHER;
+ l->looping_previously_known = true;
l->looping = false;
l->can_throw = false;
indication of possible infinite loop side
effect. */
if (mark_dfs_back_edges ())
- l->looping = true;
-
+ {
+ /* Preheaders are needed for SCEV to work.
+ Simple lateches and recorded exits improve chances that loop will
+ proved to be finite in testcases such as in loop-15.c and loop-24.c */
+ loop_optimizer_init (LOOPS_NORMAL
+ | LOOPS_HAVE_RECORDED_EXITS);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ flow_loops_dump (dump_file, NULL, 0);
+ if (mark_irreducible_loops ())
+ {
+ if (dump_file)
+ fprintf (dump_file, " has irreducible loops\n");
+ l->looping = true;
+ }
+ else
+ {
+ loop_iterator li;
+ struct loop *loop;
+ scev_initialize ();
+ FOR_EACH_LOOP (li, loop, 0)
+ if (!finite_loop_p (loop))
+ {
+ if (dump_file)
+ fprintf (dump_file, " can not prove finiteness of loop %i\n", loop->num);
+ l->looping =true;
+ break;
+ }
+ scev_finalize ();
+ }
+ loop_optimizer_finalize ();
+ }
}
if (TREE_READONLY (decl))
{
l->pure_const_state = IPA_CONST;
- l->state_set_in_source = IPA_CONST;
+ l->state_previously_known = IPA_CONST;
if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
- l->looping = false;
+ l->looping = false, l->looping_previously_known = false;
}
if (DECL_PURE_P (decl))
{
if (l->pure_const_state != IPA_CONST)
l->pure_const_state = IPA_PURE;
- l->state_set_in_source = IPA_PURE;
+ l->state_previously_known = IPA_PURE;
if (!DECL_LOOPING_CONST_OR_PURE_P (decl))
- l->looping = false;
+ l->looping = false, l->looping_previously_known = false;
}
if (TREE_NOTHROW (decl))
l->can_throw = false;
visited_nodes = NULL;
}
+static bool
+ignore_edge (struct cgraph_edge *e)
+{
+ return (!e->can_throw_external);
+}
+
+/* Return true if NODE is self recursive function. */
+
+static bool
+self_recursive_p (struct cgraph_node *node)
+{
+ struct cgraph_edge *e;
+ for (e = node->callees; e; e = e->next_callee)
+ if (e->callee == node)
+ return true;
+ return false;
+}
+
/* Produce the global information by preforming a transitive closure
on the local information that was produced by generate_summary.
Note that there is no function_transform pass since this only
cgraph_remove_function_insertion_hook (function_insertion_hook_holder);
cgraph_remove_node_duplication_hook (node_duplication_hook_holder);
cgraph_remove_node_removal_hook (node_removal_hook_holder);
- order_pos = ipa_utils_reduced_inorder (order, true, false);
+ order_pos = ipa_utils_reduced_inorder (order, true, false, NULL);
if (dump_file)
{
dump_cgraph (dump_file);
{
enum pure_const_state_e pure_const_state = IPA_CONST;
bool looping = false;
- bool can_throw = false;
int count = 0;
node = order[i];
if (pure_const_state < w_l->pure_const_state)
pure_const_state = w_l->pure_const_state;
- if (w_l->can_throw)
- can_throw = true;
if (w_l->looping)
looping = true;
- if (pure_const_state == IPA_NEITHER
- && can_throw)
+ if (pure_const_state == IPA_NEITHER)
break;
count++;
funct_state y_l = get_function_state (y);
if (pure_const_state < y_l->pure_const_state)
pure_const_state = y_l->pure_const_state;
- if (pure_const_state == IPA_NEITHER
- && can_throw)
+ if (pure_const_state == IPA_NEITHER)
break;
if (y_l->looping)
looping = true;
- if (y_l->can_throw && !TREE_NOTHROW (w->decl)
- /* FIXME: We should check that the throw can get external.
- We also should handle only loops formed by can throw external
- edges. */)
- can_throw = true;
}
}
w_info = (struct ipa_dfs_info *) w->aux;
enum pure_const_state_e this_state = pure_const_state;
bool this_looping = looping;
- if (w_l->state_set_in_source != IPA_NEITHER)
- {
- if (this_state > w_l->state_set_in_source)
- this_state = w_l->state_set_in_source;
- this_looping = false;
- }
+ if (w_l->state_previously_known != IPA_NEITHER
+ && this_state > w_l->state_previously_known)
+ this_state = w_l->state_previously_known;
+ if (!this_looping && self_recursive_p (w))
+ this_looping = true;
+ if (!w_l->looping_previously_known)
+ this_looping = false;
/* All nodes within a cycle share the same info. */
w_l->pure_const_state = this_state;
default:
break;
}
+ w_info = (struct ipa_dfs_info *) w->aux;
+ w = w_info->next_cycle;
+ }
+ }
+
+ /* Cleanup. */
+ for (node = cgraph_nodes; node; node = node->next)
+ {
+ /* Get rid of the aux information. */
+ if (node->aux)
+ {
+ w_info = (struct ipa_dfs_info *) node->aux;
+ free (node->aux);
+ node->aux = NULL;
+ }
+ }
+ order_pos = ipa_utils_reduced_inorder (order, true, false, ignore_edge);
+ if (dump_file)
+ {
+ dump_cgraph (dump_file);
+ ipa_utils_print_order(dump_file, "reduced for nothrow", order, order_pos);
+ }
+ /* Propagate the local information thru the call graph to produce
+ the global information. All the nodes within a cycle will have
+ the same info so we collapse cycles first. Then we can do the
+ propagation in one pass from the leaves to the roots. */
+ for (i = 0; i < order_pos; i++ )
+ {
+ bool can_throw = false;
+ node = order[i];
+
+ /* Find the worst state for any node in the cycle. */
+ w = node;
+ while (w)
+ {
+ struct cgraph_edge *e;
+ funct_state w_l = get_function_state (w);
+
+ if (w_l->can_throw)
+ can_throw = true;
+
+ if (can_throw)
+ break;
+
+ for (e = w->callees; e; e = e->next_callee)
+ {
+ struct cgraph_node *y = e->callee;
+
+ if (cgraph_function_body_availability (y) > AVAIL_OVERWRITABLE)
+ {
+ funct_state y_l = get_function_state (y);
+
+ if (can_throw)
+ break;
+ if (y_l->can_throw && !TREE_NOTHROW (w->decl)
+ && e->can_throw_external)
+ can_throw = true;
+ }
+ }
+ w_info = (struct ipa_dfs_info *) w->aux;
+ w = w_info->next_cycle;
+ }
+
+ /* Copy back the region's pure_const_state which is shared by
+ all nodes in the region. */
+ w = node;
+ while (w)
+ {
+ funct_state w_l = get_function_state (w);
if (!can_throw && !TREE_NOTHROW (w->decl))
{
- /* FIXME: TREE_NOTHROW is not set because passmanager will execute
- verify_ssa and verify_cfg on every function. Before fixup_cfg is done,
- those functions are going to have NOTHROW calls in EH regions reulting
- in ICE. */
+ struct cgraph_edge *e;
+ TREE_NOTHROW (w->decl) = true;
+ for (e = w->callers; e; e = e->next_caller)
+ e->can_throw_external = false;
if (dump_file)
fprintf (dump_file, "Function found to be nothrow: %s\n",
cgraph_node_name (w));
}
+ else if (can_throw && !TREE_NOTHROW (w->decl))
+ w_l->can_throw = true;
w_info = (struct ipa_dfs_info *) w->aux;
w = w_info->next_cycle;
}
&& !(errorcount || sorrycount));
}
-struct ipa_opt_pass pass_ipa_pure_const =
+struct ipa_opt_pass_d pass_ipa_pure_const =
{
{
IPA_PASS,
}
if (!l->can_throw && !TREE_NOTHROW (current_function_decl))
{
- TREE_NOTHROW (current_function_decl) = 1;
+ struct cgraph_edge *e;
+
+ TREE_NOTHROW (current_function_decl) = true;
+ for (e = cgraph_node (current_function_decl)->callers;
+ e; e = e->next_caller)
+ e->can_throw_external = false;
changed = true;
if (dump_file)
fprintf (dump_file, "Function found to be nothrow: %s\n",