#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
-#include "ggc.h"
-#include "tree.h"
-#include "basic-block.h"
-#include "tree-pretty-print.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;
return chrec_dont_know;
}
-/* Determine whether the CHREC is always positive/negative. If the expression
- cannot be statically analyzed, return false, otherwise set the answer into
- VALUE. */
-
-bool
-chrec_is_positive (tree chrec, bool *value)
-{
- bool value0, value1, value2;
- tree end_value, nb_iter;
-
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
- || !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
- return false;
-
- /* FIXME -- overflows. */
- if (value0 == value1)
- {
- *value = value0;
- return true;
- }
-
- /* Otherwise the chrec is under the form: "{-197, +, 2}_1",
- and the proof consists in showing that the sign never
- changes during the execution of the loop, from 0 to
- loop->nb_iterations. */
- if (!evolution_function_is_affine_p (chrec))
- return false;
-
- nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
- if (chrec_contains_undetermined (nb_iter))
- return false;
-
-#if 0
- /* TODO -- If the test is after the exit, we may decrease the number of
- iterations by one. */
- if (after_exit)
- nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
-#endif
-
- end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
-
- if (!chrec_is_positive (end_value, &value2))
- return false;
-
- *value = value0;
- return value0 == value1;
-
- case INTEGER_CST:
- *value = (tree_int_cst_sgn (chrec) == 1);
- return true;
-
- default:
- return false;
- }
-}
-
/* Associate CHREC to SCALAR. */
static void
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);
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);
else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
new_init = CHREC_LEFT (res);
STRIP_USELESS_TYPE_CONVERSION (new_init);
- gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC);
- if (!operand_equal_p (init_cond, new_init, 0))
+ if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
+ || !operand_equal_p (init_cond, new_init, 0))
return chrec_dont_know;
}
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);
may_be_zero = NULL_TREE;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
fprintf (dump_file, "(number_of_iterations_in_loop = \n");
res = chrec_dont_know;
else
res = chrec_dont_know;
- if (dump_file && (dump_flags & TDF_DETAILS))
+ if (dump_file && (dump_flags & TDF_SCEV))
{
fprintf (dump_file, " (set_nb_iterations_in_loop = ");
print_generic_expr (dump_file, res, 0);
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 ();
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
