/* Scalar evolution detector.
- Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "tree.h"
-#include "real.h"
-
-/* These RTL headers are needed for basic-block.h. */
-#include "rtl.h"
-#include "basic-block.h"
-#include "diagnostic.h"
+#include "gimple-pretty-print.h"
#include "tree-flow.h"
-#include "tree-dump.h"
-#include "timevar.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
-#include "flags.h"
#include "params.h"
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
{
struct scev_info_str *res;
- res = GGC_NEW (struct scev_info_str);
+ res = ggc_alloc_scev_info_str ();
res->var = var;
res->chrec = chrec_not_analyzed_yet;
res->instantiated_below = instantiated_below;
if (is_gimple_min_invariant (chrec))
return false;
- if (TREE_CODE (chrec) == VAR_DECL
- || TREE_CODE (chrec) == PARM_DECL
- || TREE_CODE (chrec) == FUNCTION_DECL
- || TREE_CODE (chrec) == LABEL_DECL
- || TREE_CODE (chrec) == RESULT_DECL
- || TREE_CODE (chrec) == FIELD_DECL)
- return true;
-
if (TREE_CODE (chrec) == SSA_NAME)
{
- gimple def = SSA_NAME_DEF_STMT (chrec);
- struct loop *def_loop = loop_containing_stmt (def);
- struct loop *loop = get_loop (loop_nb);
+ gimple def;
+ loop_p def_loop, loop;
+
+ if (SSA_NAME_IS_DEFAULT_DEF (chrec))
+ return false;
+
+ def = SSA_NAME_DEF_STMT (chrec);
+ def_loop = loop_containing_stmt (def);
+ loop = get_loop (loop_nb);
if (def_loop == NULL)
return false;
if (dump_file)
{
- if (dump_flags & TDF_DETAILS)
+ if (dump_flags & TDF_SCEV)
{
fprintf (dump_file, "(set_scalar_evolution \n");
fprintf (dump_file, " instantiated_below = %d \n",
if (dump_file)
{
- if (dump_flags & TDF_DETAILS)
+ if (dump_flags & TDF_SCEV)
{
fprintf (dump_file, "(get_scalar_evolution \n");
fprintf (dump_file, " (scalar = ");
break;
}
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (scalar_evolution = ");
print_generic_expr (dump_file, res, 0);
/* This should not happen. */
return chrec_dont_know;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(add_to_evolution \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
return res;
}
-/* Helper function. */
-
-static inline tree
-set_nb_iterations_in_loop (struct loop *loop,
- tree res)
-{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " (set_nb_iterations_in_loop = ");
- print_generic_expr (dump_file, res, 0);
- fprintf (dump_file, "))\n");
- }
-
- loop->nb_iterations = res;
- return res;
-}
-
\f
/* This section selects the loops that will be good candidates for the
gimple res = NULL;
edge exit_edge = single_exit (loop);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
fprintf (dump_file, "(get_loop_exit_condition \n ");
if (exit_edge)
res = stmt;
}
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
print_gimple_stmt (dump_file, res, 0, 0);
fprintf (dump_file, ")\n");
halting_phi, evolution_of_loop, limit);
break;
+ case ADDR_EXPR:
+ /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
+ if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF)
+ {
+ expr = TREE_OPERAND (expr, 0);
+ rhs0 = TREE_OPERAND (expr, 0);
+ rhs1 = TREE_OPERAND (expr, 1);
+ type = TREE_TYPE (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs0);
+ STRIP_USELESS_TYPE_CONVERSION (rhs1);
+ res = follow_ssa_edge_binary (loop, at_stmt, type,
+ rhs0, POINTER_PLUS_EXPR, rhs1,
+ halting_phi, evolution_of_loop, limit);
+ }
+ else
+ res = t_false;
+ break;
+
case ASSERT_EXPR:
/* This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"
It must be handled as a copy assignment of the form a_1 = a_2. */
return t_false;
/* Give up if the path is longer than the MAX that we allow. */
- if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+ if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
return t_dont_know;
def_loop = loop_containing_stmt (def);
struct loop *loop = loop_containing_stmt (loop_phi_node);
basic_block bb;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(analyze_evolution_in_loop \n");
fprintf (dump_file, " (loop_phi_node = ");
evolution_function = chrec_merge (evolution_function, ev_fn);
}
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (evolution_function = ");
print_generic_expr (dump_file, evolution_function, 0);
tree init_cond = chrec_not_analyzed_yet;
struct loop *loop = loop_containing_stmt (loop_phi_node);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(analyze_initial_condition \n");
fprintf (dump_file, " (loop_phi_node = \n");
init_cond = res;
}
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (init_cond = ");
print_generic_expr (dump_file, init_cond, 0);
init_cond = analyze_initial_condition (loop_phi_node);
res = analyze_evolution_in_loop (loop_phi_node, init_cond);
+ /* Verify we maintained the correct initial condition throughout
+ possible conversions in the SSA chain. */
+ if (res != chrec_dont_know)
+ {
+ tree new_init = res;
+ if (CONVERT_EXPR_P (res)
+ && TREE_CODE (TREE_OPERAND (res, 0)) == POLYNOMIAL_CHREC)
+ new_init = fold_convert (TREE_TYPE (res),
+ CHREC_LEFT (TREE_OPERAND (res, 0)));
+ else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
+ new_init = CHREC_LEFT (res);
+ STRIP_USELESS_TYPE_CONVERSION (new_init);
+ if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
+ || !operand_equal_p (init_cond, new_init, 0))
+ return chrec_dont_know;
+ }
+
return res;
}
return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
at_stmt);
}
-
- return chrec_dont_know;
}
switch (code)
{
+ case ADDR_EXPR:
+ /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */
+ if (TREE_CODE (TREE_OPERAND (rhs1, 0)) != MEM_REF)
+ {
+ res = chrec_dont_know;
+ break;
+ }
+
+ rhs2 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 1);
+ rhs1 = TREE_OPERAND (TREE_OPERAND (rhs1, 0), 0);
+ /* Fall through. */
+
case POINTER_PLUS_EXPR:
chrec1 = analyze_scalar_evolution (loop, rhs1);
chrec2 = analyze_scalar_evolution (loop, rhs2);
chrec1 = chrec_convert (type, chrec1, at_stmt);
- chrec2 = chrec_convert (sizetype, chrec2, at_stmt);
+ chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
res = chrec_fold_plus (type, chrec1, chrec2);
break;
if (automatically_generated_chrec_p (expr))
return expr;
- if (TREE_CODE (expr) == POLYNOMIAL_CHREC)
+ if (TREE_CODE (expr) == POLYNOMIAL_CHREC
+ || get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
return chrec_dont_know;
extract_ops_from_tree (expr, &code, &op0, &op1);
struct loop *def_loop,
tree ev)
{
+ bool val;
tree res;
+
if (def_loop == wrto_loop)
return ev;
def_loop = superloop_at_depth (def_loop, loop_depth (wrto_loop) + 1);
res = compute_overall_effect_of_inner_loop (def_loop, ev);
+ if (no_evolution_in_loop_p (res, wrto_loop->num, &val) && val)
+ return res;
+
return analyze_scalar_evolution_1 (wrto_loop, res, chrec_not_analyzed_yet);
}
{
tree res;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(analyze_scalar_evolution \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
res = get_scalar_evolution (block_before_loop (loop), var);
res = analyze_scalar_evolution_1 (loop, var, res);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
fprintf (dump_file, ")\n");
return res;
result again. */
res = analyze_scalar_evolution (def_loop, chrec);
- /* Don't instantiate loop-closed-ssa phi nodes. */
+ /* Don't instantiate default definitions. */
if (TREE_CODE (res) == SSA_NAME
- && (loop_containing_stmt (SSA_NAME_DEF_STMT (res)) == NULL
- || (loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
- > loop_depth (def_loop))))
+ && SSA_NAME_IS_DEFAULT_DEF (res))
+ ;
+
+ /* Don't instantiate loop-closed-ssa phi nodes. */
+ else if (TREE_CODE (res) == SSA_NAME
+ && loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
+ > loop_depth (def_loop))
{
if (res == chrec)
res = loop_closed_phi_def (chrec);
else
res = chrec;
- if (res == NULL_TREE
- || !dominated_by_p (CDI_DOMINATORS, instantiate_below,
- gimple_bb (SSA_NAME_DEF_STMT (res))))
+ /* When there is no loop_closed_phi_def, it means that the
+ variable is not used after the loop: try to still compute the
+ value of the variable when exiting the loop. */
+ if (res == NULL_TREE)
+ {
+ loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
+ res = analyze_scalar_evolution (loop, chrec);
+ res = compute_overall_effect_of_inner_loop (loop, res);
+ res = instantiate_scev_r (instantiate_below, evolution_loop, res,
+ fold_conversions, cache, size_expr);
+ }
+ else if (!dominated_by_p (CDI_DOMINATORS, instantiate_below,
+ gimple_bb (SSA_NAME_DEF_STMT (res))))
res = chrec_dont_know;
}
/* Store the correct value to the cache. */
set_instantiated_value (cache, instantiate_below, chrec, res);
return res;
-
}
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
and EVOLUTION_LOOP, that were left under a symbolic form.
+ "CHREC" is an array reference to be instantiated.
+
+ CACHE is the cache of already instantiated values.
+
+ FOLD_CONVERSIONS should be set to true when the conversions that
+ may wrap in signed/pointer type are folded, as long as the value of
+ the chrec is preserved.
+
+ SIZE_EXPR is used for computing the size of the expression to be
+ instantiated, and to stop if it exceeds some limit. */
+
+static tree
+instantiate_array_ref (basic_block instantiate_below,
+ struct loop *evolution_loop, tree chrec,
+ bool fold_conversions, htab_t cache, int size_expr)
+{
+ tree res;
+ tree index = TREE_OPERAND (chrec, 1);
+ tree op1 = instantiate_scev_r (instantiate_below, evolution_loop, index,
+ fold_conversions, cache, size_expr);
+
+ if (op1 == chrec_dont_know)
+ return chrec_dont_know;
+
+ if (chrec && op1 == index)
+ return chrec;
+
+ res = unshare_expr (chrec);
+ TREE_OPERAND (res, 1) = op1;
+ return res;
+}
+
+/* Analyze all the parameters of the chrec, between INSTANTIATE_BELOW
+ and EVOLUTION_LOOP, that were left under a symbolic form.
+
"CHREC" that stands for a convert expression "(TYPE) OP" is to be
instantiated.
if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
return chrec_dont_know;
- if (automatically_generated_chrec_p (chrec)
+ if (chrec == NULL_TREE
+ || automatically_generated_chrec_p (chrec)
|| is_gimple_min_invariant (chrec))
return chrec;
TREE_OPERAND (chrec, 0),
fold_conversions, cache, size_expr);
+ case ADDR_EXPR:
case SCEV_NOT_KNOWN:
return chrec_dont_know;
case SCEV_KNOWN:
return chrec_known;
+ case ARRAY_REF:
+ return instantiate_array_ref (instantiate_below, evolution_loop, chrec,
+ fold_conversions, cache, size_expr);
+
default:
break;
}
tree res;
htab_t cache = htab_create (10, hash_scev_info, eq_scev_info, del_scev_info);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, "(instantiate_scev \n");
fprintf (dump_file, " (instantiate_below = %d)\n", instantiate_below->index);
res = instantiate_scev_r (instantiate_below, evolution_loop, chrec, false,
cache, 0);
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
/* Entry point for the analysis of the number of iterations pass.
This function tries to safely approximate the number of iterations
the loop will run. When this property is not decidable at compile
- time, the result is chrec_dont_know. Otherwise the result is
- a scalar or a symbolic parameter.
+ time, the result is chrec_dont_know. Otherwise the result is a
+ scalar or a symbolic parameter. When the number of iterations may
+ be equal to zero and the property cannot be determined at compile
+ time, the result is a COND_EXPR that represents in a symbolic form
+ the conditions under which the number of iterations is not zero.
Example of analysis: suppose that the loop has an exit condition:
tree
number_of_latch_executions (struct loop *loop)
{
- tree res, type;
edge exit;
struct tree_niter_desc niter_desc;
+ tree may_be_zero;
+ tree res;
- /* Determine whether the number_of_iterations_in_loop has already
+ /* Determine whether the number of iterations in loop has already
been computed. */
res = loop->nb_iterations;
if (res)
return res;
- res = chrec_dont_know;
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(number_of_iterations_in_loop\n");
+ may_be_zero = NULL_TREE;
+
+ if (dump_file && (dump_flags & TDF_SCEV))
+ fprintf (dump_file, "(number_of_iterations_in_loop = \n");
+ res = chrec_dont_know;
exit = single_exit (loop);
- if (!exit)
- goto end;
- if (!number_of_iterations_exit (loop, exit, &niter_desc, false))
- goto end;
+ if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
+ {
+ may_be_zero = niter_desc.may_be_zero;
+ res = niter_desc.niter;
+ }
- type = TREE_TYPE (niter_desc.niter);
- if (integer_nonzerop (niter_desc.may_be_zero))
- res = build_int_cst (type, 0);
- else if (integer_zerop (niter_desc.may_be_zero))
- res = niter_desc.niter;
+ if (res == chrec_dont_know
+ || !may_be_zero
+ || integer_zerop (may_be_zero))
+ ;
+ else if (integer_nonzerop (may_be_zero))
+ res = build_int_cst (TREE_TYPE (res), 0);
+
+ else if (COMPARISON_CLASS_P (may_be_zero))
+ res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
+ build_int_cst (TREE_TYPE (res), 0), res);
else
res = chrec_dont_know;
-end:
- return set_nb_iterations_in_loop (loop, res);
+ if (dump_file && (dump_flags & TDF_SCEV))
+ {
+ fprintf (dump_file, " (set_nb_iterations_in_loop = ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, "))\n");
+ }
+
+ loop->nb_iterations = res;
+ return res;
}
/* Returns the number of executions of the exit condition of LOOP,
unsigned nb_static_loops = 0;
gimple cond;
- for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
+ FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
{
tree res = number_of_latch_executions (loop_containing_stmt (cond));
if (chrec_contains_undetermined (res))
reset_chrecs_counters (&stats);
- for (i = 0; VEC_iterate (gimple, *exit_conditions, i, cond); i++)
+ FOR_EACH_VEC_ELT (gimple, *exit_conditions, i, cond)
{
struct loop *loop;
basic_block bb;
loop_iterator li;
struct loop *loop;
- scalar_evolution_info = htab_create_alloc (100,
- hash_scev_info,
- eq_scev_info,
- del_scev_info,
- ggc_calloc,
- ggc_free);
+
+ scalar_evolution_info = htab_create_ggc (100, hash_scev_info, eq_scev_info,
+ del_scev_info);
initialize_scalar_evolutions_analyzer ();
}
}
-/* Cleans up the information cached by the scalar evolutions analysis. */
+/* Cleans up the information cached by the scalar evolutions analysis
+ in the hash table. */
+
+void
+scev_reset_htab (void)
+{
+ if (!scalar_evolution_info)
+ return;
+
+ htab_empty (scalar_evolution_info);
+}
+
+/* Cleans up the information cached by the scalar evolutions analysis
+ in the hash table and in the loop->nb_iterations. */
void
scev_reset (void)
loop_iterator li;
struct loop *loop;
- if (!scalar_evolution_info || !current_loops)
+ scev_reset_htab ();
+
+ if (!current_loops)
return;
- htab_empty (scalar_evolution_info);
FOR_EACH_LOOP (li, loop, 0)
{
loop->nb_iterations = NULL_TREE;
iv->no_overflow = false;
type = TREE_TYPE (op);
- if (TREE_CODE (type) != INTEGER_TYPE
- && TREE_CODE (type) != POINTER_TYPE)
+ if (!POINTER_TYPE_P (type)
+ && !INTEGRAL_TYPE_P (type))
return false;
ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
OSDN Git Service
