/* 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
variable T is legal in a function that is either pure or const. */
static inline void
-check_op (funct_state local,
- tree t, bool checking_write)
+check_op (funct_state local, tree t, bool checking_write)
{
- while (t && handled_component_p (t))
- t = TREE_OPERAND (t, 0);
- if (!t)
- return;
- if (INDIRECT_REF_P (t) || TREE_CODE (t) == TARGET_MEM_REF)
+ t = get_base_address (t);
+ if (t && TREE_THIS_VOLATILE (t))
{
- if (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 (checking_write)
- {
- local->pure_const_state = IPA_NEITHER;
- if (dump_file)
- fprintf (dump_file, " Indirect ref write is not const/pure\n");
- return;
- }
- else
- {
- if (dump_file)
- fprintf (dump_file, " Indirect ref read is not const\n");
- if (local->pure_const_state == IPA_CONST)
- local->pure_const_state = IPA_PURE;
- }
+ 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, " Indirect ref write is not const/pure\n");
+ return;
+ }
+ else
+ {
+ if (dump_file)
+ fprintf (dump_file, " Indirect ref read is not const\n");
+ if (local->pure_const_state == IPA_CONST)
+ local->pure_const_state = IPA_PURE;
}
}
/* Direct functions calls are handled by IPA propagation. */
}
+/* Wrapper around check_decl for loads. */
+
+static bool
+check_load (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
+{
+ if (DECL_P (op))
+ check_decl ((funct_state)data, op, false);
+ else
+ check_op ((funct_state)data, op, false);
+ return false;
+}
+
+/* Wrapper around check_decl for stores. */
+
+static bool
+check_store (gimple stmt ATTRIBUTE_UNUSED, tree op, void *data)
+{
+ if (DECL_P (op))
+ check_decl ((funct_state)data, op, true);
+ else
+ check_op ((funct_state)data, op, true);
+ return false;
+}
+
/* Look into pointer pointed to by GSIP and figure out what interesting side
effects it has. */
static void
print_gimple_stmt (dump_file, stmt, 0, 0);
}
- /* Look for direct loads and stores. */
- if (gimple_has_lhs (stmt))
- {
- tree lhs = get_base_address (gimple_get_lhs (stmt));
- if (lhs && DECL_P (lhs))
- check_decl (local, lhs, true);
- }
- if (gimple_assign_single_p (stmt))
- {
- tree rhs = get_base_address (gimple_assign_rhs1 (stmt));
- if (rhs && DECL_P (rhs))
- check_decl (local, rhs, false);
- }
- else if (is_gimple_call (stmt))
- {
- for (i = 0; i < gimple_call_num_args (stmt); ++i)
- {
- tree rhs = get_base_address (gimple_call_arg (stmt, i));
- if (rhs && DECL_P (rhs))
- check_decl (local, rhs, false);
- }
- }
- else if (gimple_code (stmt) == GIMPLE_ASM)
- {
- for (i = 0; i < gimple_asm_ninputs (stmt); ++i)
- {
- tree op = TREE_VALUE (gimple_asm_input_op (stmt, i));
- op = get_base_address (op);
- if (op && DECL_P (op))
- check_decl (local, op, false);
- }
- for (i = 0; i < gimple_asm_noutputs (stmt); ++i)
- {
- tree op = TREE_VALUE (gimple_asm_output_op (stmt, i));
- op = get_base_address (op);
- if (op && DECL_P (op))
- check_decl (local, op, true);
- }
- }
+ /* Look for loads and stores. */
+ walk_stmt_load_store_ops (stmt, local, check_load, check_store);
if (gimple_code (stmt) != GIMPLE_CALL
&& stmt_could_throw_p (stmt))
}
switch (gimple_code (stmt))
{
- case GIMPLE_ASSIGN:
- check_op (local, gimple_assign_lhs (stmt), true);
- i = 1;
- break;
case GIMPLE_CALL:
- check_op (local, gimple_call_lhs (stmt), true);
- i = 1;
check_call (local, stmt, ipa);
break;
case GIMPLE_LABEL:
}
break;
case GIMPLE_ASM:
- for (i = 0; i < gimple_asm_noutputs (stmt); i++)
- check_op (local, TREE_VALUE (gimple_asm_output_op (stmt, i)), true);
- for (i = 0; i < gimple_asm_ninputs (stmt); i++)
- check_op (local, TREE_VALUE (gimple_asm_input_op (stmt, i)), false);
for (i = 0; i < gimple_asm_nclobbers (stmt); i++)
{
tree op = gimple_asm_clobber_op (stmt, i);
default:
break;
}
-
- for (; i < gimple_num_ops (stmt); i++)
- check_op (local, gimple_op (stmt, i), false);
}
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);
+}
+
/* 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 (!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",