/* 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 "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 "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
{
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;
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
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. */
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);
+ gcc_assert (TREE_CODE (new_init) != POLYNOMIAL_CHREC);
+ if (!operand_equal_p (init_cond, new_init, 0))
+ return chrec_dont_know;
+ }
+
return res;
}
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;
}
/* 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;
+
+ may_be_zero = NULL_TREE;
if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "(number_of_iterations_in_loop\n");
+ 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;
+ }
+
+ 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);
- 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;
+ 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_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;
}
/* Returns the number of executions of the exit condition of LOOP,
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;