This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] for PR 26304
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 8 May 2006 13:13:42 +0200
- Subject: [patch] for PR 26304
Hello,
this bug is caused by a problem with handling of variables with negative
step in infer_loop_bounds_from_undefined (handling of the fact that
"signed arithmetics does not overflow" in case step is negative) -- we
ended up inferring that the loop rolls at most once, thus the variable
[5,+,-1] is always positive.
When fixing the bug, I also noticed a number of off-by-one errors
arising because there is a difference between the way the estimates
obtained from # of iterations analysis and from undefined behavior
need to be handled:
-- if an exit statement S is executed at most X times, everything before
S is executed at most X times and everything after it at most X-1 times
-- if we infer that some statement S can be executed at most X times
before invoking undefined behavior, we know that everything before S
(more precisely, before the first exit before S) can be executed at
most X+1 times, and everything after S can be exeecuted at most X
times.
This patch fixes both problems. Bootstrapped & regtested on
ppc64-linux, x86_64 and i686.
Zdenek
PR tree-optimization/26304
* tree-ssa-loop-niter.c (record_estimate): Take is_exit argument.
(record_nonwrapping_iv): New function.
(compute_estimated_nb_iterations): Change test whether bound is
INTEGER_CST to assert.
(idx_infer_loop_bounds, infer_loop_bounds_from_ref,
infer_loop_bounds_from_array, infer_loop_bounds_from_signedness,
(infer_loop_bounds_from_undefined): Use infer_loop_bounds_from_array
and infer_loop_bounds_from_signedness.
(estimate_numbers_of_iterations_loop): Always call
infer_loop_bounds_from_undefined and compute_estimated_nb_iterations.
(n_of_executions_at_most): Differ between the estimates coming from
# of iteration analysis and from infer_loop_bounds_from_undefined.
* tree-data-ref.c (estimate_niter_from_size_of_data,
estimate_iters_using_array): Removed.
(analyze_array_indexes): Do not use it for estimation of # of
iterations.
(analyze_array): Do not pass estimate_only argument to
analyze_array_indexes.
* tree-data-ref.h (estimate_iters_using_array): Declaration removed.
* cfgloop.h (struct nb_iter_bound): Add is_exit field. Update
comments.
(record_estimate): Declaration removed.
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c (revision 113549)
--- tree-ssa-loop-niter.c (working copy)
*************** derive_constant_upper_bound (tree val, t
*** 1482,1513 ****
return fold_convert (unsigned_type, val);
}
! /* Records that AT_STMT is executed at most BOUND times in LOOP. The
! additional condition ADDITIONAL is recorded with the bound. */
! void
! record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
{
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
tree c_bound = derive_constant_upper_bound (bound, additional);
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Statements after ");
print_generic_expr (dump_file, at_stmt, TDF_SLIM);
! fprintf (dump_file, " are executed at most ");
print_generic_expr (dump_file, bound, TDF_SLIM);
fprintf (dump_file, " (bounded by ");
print_generic_expr (dump_file, c_bound, TDF_SLIM);
! fprintf (dump_file, ") times in loop %d.\n", loop->num);
}
elt->bound = c_bound;
! elt->at_stmt = at_stmt;
elt->next = loop->bounds;
loop->bounds = elt;
}
/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
approximation of the number of iterations for LOOP. */
--- 1499,1587 ----
return fold_convert (unsigned_type, val);
}
! /* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. The
! additional condition ADDITIONAL is recorded with the bound. IS_EXIT
! is true if the loop is exited immediately after STMT, and this exit
! is taken at last when the STMT is executed BOUND + 1 times. */
! static void
! record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt,
! bool is_exit)
{
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
tree c_bound = derive_constant_upper_bound (bound, additional);
if (dump_file && (dump_flags & TDF_DETAILS))
{
! fprintf (dump_file, "Statement %s", is_exit ? "(exit)" : "");
print_generic_expr (dump_file, at_stmt, TDF_SLIM);
! fprintf (dump_file, " is executed at most ");
print_generic_expr (dump_file, bound, TDF_SLIM);
fprintf (dump_file, " (bounded by ");
print_generic_expr (dump_file, c_bound, TDF_SLIM);
! fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
}
elt->bound = c_bound;
! elt->stmt = at_stmt;
! elt->is_exit = is_exit;
elt->next = loop->bounds;
loop->bounds = elt;
}
+ /* Record the estimate on number of iterations of LOOP based on the fact that
+ the induction variable BASE + STEP * i evaluated in STMT does not wrap and
+ its values belong to the range <LOW, HIGH>. */
+
+ static void
+ record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
+ tree low, tree high)
+ {
+ tree niter_bound, extreme, delta;
+ tree type = TREE_TYPE (base), unsigned_type;
+
+ if (TREE_CODE (step) != INTEGER_CST || zero_p (step))
+ return;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Induction variable (");
+ print_generic_expr (dump_file, TREE_TYPE (base), TDF_SLIM);
+ fprintf (dump_file, ") ");
+ print_generic_expr (dump_file, base, TDF_SLIM);
+ fprintf (dump_file, " + ");
+ print_generic_expr (dump_file, step, TDF_SLIM);
+ fprintf (dump_file, " * iteration does not wrap in statement ");
+ print_generic_expr (dump_file, stmt, TDF_SLIM);
+ fprintf (dump_file, " in loop %d.\n", loop->num);
+ }
+
+ unsigned_type = unsigned_type_for (type);
+ base = fold_convert (unsigned_type, base);
+ step = fold_convert (unsigned_type, step);
+
+ if (tree_int_cst_sign_bit (step))
+ {
+ extreme = fold_convert (unsigned_type, low);
+ delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
+ step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
+ if (TREE_CODE (base) != INTEGER_CST)
+ base = fold_convert (unsigned_type, high);
+ }
+ else
+ {
+ extreme = fold_convert (unsigned_type, high);
+ delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
+ if (TREE_CODE (base) != INTEGER_CST)
+ base = fold_convert (unsigned_type, low);
+ }
+
+ /* STMT is executed at most NITER_BOUND + 1 times, since otherwise the value
+ would get out of the range. */
+ niter_bound = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step);
+ record_estimate (loop, niter_bound, NULL_TREE, stmt, false);
+ }
+
/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
approximation of the number of iterations for LOOP. */
*************** compute_estimated_nb_iterations (struct
*** 1518,1525 ****
for (bound = loop->bounds; bound; bound = bound->next)
{
! if (TREE_CODE (bound->bound) != INTEGER_CST)
! continue;
/* Update only when there is no previous estimation, or when the current
estimation is smaller. */
--- 1592,1598 ----
for (bound = loop->bounds; bound; bound = bound->next)
{
! gcc_assert (TREE_CODE (bound->bound) == INTEGER_CST);
/* Update only when there is no previous estimation, or when the current
estimation is smaller. */
*************** compute_estimated_nb_iterations (struct
*** 1529,1534 ****
--- 1602,1766 ----
}
}
+ /* Determine information about number of iterations a LOOP from the index
+ IDX of a data reference accessed in STMT. Callback for for_each_index. */
+
+ struct ilb_data
+ {
+ struct loop *loop;
+ tree stmt;
+ };
+
+ static bool
+ idx_infer_loop_bounds (tree base, tree *idx, void *dta)
+ {
+ struct ilb_data *data = dta;
+ tree ev, init, step;
+ tree low, high, type, next;
+ bool sign;
+ struct loop *loop = data->loop;
+
+ if (TREE_CODE (base) != ARRAY_REF)
+ return true;
+
+ ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, *idx));
+ init = initial_condition (ev);
+ step = evolution_part_in_loop_num (ev, loop->num);
+
+ if (!init
+ || !step
+ || TREE_CODE (step) != INTEGER_CST
+ || zero_p (step)
+ || tree_contains_chrecs (init, NULL)
+ || chrec_contains_symbols_defined_in_loop (init, loop->num))
+ return true;
+
+ low = array_ref_low_bound (base);
+ high = array_ref_up_bound (base);
+
+ /* The case of nonconstant bounds could be handled, but it would be
+ complicated. */
+ if (TREE_CODE (low) != INTEGER_CST
+ || !high
+ || TREE_CODE (high) != INTEGER_CST)
+ return true;
+ sign = tree_int_cst_sign_bit (step);
+ type = TREE_TYPE (step);
+
+ /* In case the relevant bound of the array does not fit in type, or
+ it does, but bound + step (in type) still belongs into the range of the
+ array, the index may wrap and still stay within the range of the array
+ (consider e.g. if the array is indexed by the full range of
+ unsigned char).
+
+ To make things simpler, we require both bounds to fit into type, although
+ there are cases where this would not be strightly necessary. */
+ if (!int_fits_type_p (high, type)
+ || !int_fits_type_p (low, type))
+ return true;
+ low = fold_convert (type, low);
+ high = fold_convert (type, high);
+
+ if (sign)
+ next = fold_binary (PLUS_EXPR, type, low, step);
+ else
+ next = fold_binary (PLUS_EXPR, type, high, step);
+
+ if (tree_int_cst_compare (low, next) <= 0
+ && tree_int_cst_compare (next, high) <= 0)
+ return true;
+
+ record_nonwrapping_iv (loop, init, step, data->stmt, low, high);
+ return true;
+ }
+
+ /* Determine information about number of iterations a LOOP from the bounds
+ of arrays in the data reference REF accessed in STMT. */
+
+ static void
+ infer_loop_bounds_from_ref (struct loop *loop, tree stmt, tree ref)
+ {
+ struct ilb_data data;
+
+ data.loop = loop;
+ data.stmt = stmt;
+ for_each_index (&ref, idx_infer_loop_bounds, &data);
+ }
+
+ /* Determine information about number of iterations of a LOOP from the way
+ arrays are used in STMT. */
+
+ static void
+ infer_loop_bounds_from_array (struct loop *loop, tree stmt)
+ {
+ tree call;
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ tree op0 = TREE_OPERAND (stmt, 0);
+ tree op1 = TREE_OPERAND (stmt, 1);
+
+ /* For each memory access, analyze its access function
+ and record a bound on the loop iteration domain. */
+ if (REFERENCE_CLASS_P (op0))
+ infer_loop_bounds_from_ref (loop, stmt, op0);
+
+ if (REFERENCE_CLASS_P (op1))
+ infer_loop_bounds_from_ref (loop, stmt, op1);
+ }
+
+
+ call = get_call_expr_in (stmt);
+ if (call)
+ {
+ tree args;
+
+ for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
+ if (REFERENCE_CLASS_P (TREE_VALUE (args)))
+ infer_loop_bounds_from_ref (loop, stmt, TREE_VALUE (args));
+ }
+ }
+
+ /* Determine information about number of iterations of a LOOP from the fact
+ that signed arithmetics in STMT does not overflow. */
+
+ static void
+ infer_loop_bounds_from_signedness (struct loop *loop, tree stmt)
+ {
+ tree def, base, step, scev, type, low, high;
+
+ if (flag_wrapv || TREE_CODE (stmt) != MODIFY_EXPR)
+ return;
+
+ def = TREE_OPERAND (stmt, 0);
+
+ if (TREE_CODE (def) != SSA_NAME)
+ return;
+
+ type = TREE_TYPE (def);
+ if (!INTEGRAL_TYPE_P (type)
+ || TYPE_UNSIGNED (type))
+ return;
+
+ scev = instantiate_parameters (loop, analyze_scalar_evolution (loop, def));
+ if (chrec_contains_undetermined (scev))
+ return;
+
+ base = initial_condition_in_loop_num (scev, loop->num);
+ step = evolution_part_in_loop_num (scev, loop->num);
+
+ if (!base || !step
+ || TREE_CODE (step) != INTEGER_CST
+ || tree_contains_chrecs (base, NULL)
+ || chrec_contains_symbols_defined_in_loop (base, loop->num))
+ return;
+
+ low = lower_bound_in_type (type, type);
+ high = upper_bound_in_type (type, type);
+
+ record_nonwrapping_iv (loop, base, step, stmt, low, high);
+ }
+
/* The following analyzers are extracting informations on the bounds
of LOOP from the following undefined behaviors:
*************** static void
*** 1542,1549 ****
infer_loop_bounds_from_undefined (struct loop *loop)
{
unsigned i;
! basic_block bb, *bbs;
block_stmt_iterator bsi;
bbs = get_loop_body (loop);
--- 1774,1782 ----
infer_loop_bounds_from_undefined (struct loop *loop)
{
unsigned i;
! basic_block *bbs;
block_stmt_iterator bsi;
+ basic_block bb;
bbs = get_loop_body (loop);
*************** infer_loop_bounds_from_undefined (struct
*** 1551,1643 ****
{
bb = bbs[i];
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! {
tree stmt = bsi_stmt (bsi);
! switch (TREE_CODE (stmt))
! {
! case MODIFY_EXPR:
! {
! tree op0 = TREE_OPERAND (stmt, 0);
! tree op1 = TREE_OPERAND (stmt, 1);
!
! /* For each array access, analyze its access function
! and record a bound on the loop iteration domain. */
! if (TREE_CODE (op1) == ARRAY_REF
! && !array_ref_contains_indirect_ref (op1))
! estimate_iters_using_array (stmt, op1);
!
! if (TREE_CODE (op0) == ARRAY_REF
! && !array_ref_contains_indirect_ref (op0))
! estimate_iters_using_array (stmt, op0);
!
! /* For each signed type variable in LOOP, analyze its
! scalar evolution and record a bound of the loop
! based on the type's ranges. */
! else if (!flag_wrapv && TREE_CODE (op0) == SSA_NAME)
! {
! tree init, step, diff, estimation;
! tree scev = instantiate_parameters
! (loop, analyze_scalar_evolution (loop, op0));
! tree type = chrec_type (scev);
! tree utype;
!
! if (chrec_contains_undetermined (scev)
! || TYPE_UNSIGNED (type))
! break;
!
! init = initial_condition_in_loop_num (scev, loop->num);
! step = evolution_part_in_loop_num (scev, loop->num);
!
! if (init == NULL_TREE
! || step == NULL_TREE
! || TREE_CODE (init) != INTEGER_CST
! || TREE_CODE (step) != INTEGER_CST
! || TYPE_MIN_VALUE (type) == NULL_TREE
! || TYPE_MAX_VALUE (type) == NULL_TREE)
! break;
!
! utype = unsigned_type_for (type);
! if (tree_int_cst_lt (step, integer_zero_node))
! diff = fold_build2 (MINUS_EXPR, utype, init,
! TYPE_MIN_VALUE (type));
! else
! diff = fold_build2 (MINUS_EXPR, utype,
! TYPE_MAX_VALUE (type), init);
!
! if (!integer_zerop (step))
! {
! estimation = fold_build2 (CEIL_DIV_EXPR, utype, diff,
! step);
! record_estimate (loop, estimation, boolean_true_node,
! stmt);
! }
! }
!
! break;
! }
!
! case CALL_EXPR:
! {
! tree args;
!
! for (args = TREE_OPERAND (stmt, 1); args;
! args = TREE_CHAIN (args))
! if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
! && !array_ref_contains_indirect_ref (TREE_VALUE (args)))
! estimate_iters_using_array (stmt, TREE_VALUE (args));
!
! break;
! }
!
! default:
! break;
! }
}
}
- compute_estimated_nb_iterations (loop);
free (bbs);
}
--- 1784,1803 ----
{
bb = bbs[i];
+ /* If BB is not executed in each iteration of the loop, we cannot
+ use it to infer any information about # of iterations of the loop. */
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
+ continue;
+
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! {
tree stmt = bsi_stmt (bsi);
! infer_loop_bounds_from_array (loop, stmt);
! infer_loop_bounds_from_signedness (loop, stmt);
}
}
free (bbs);
}
*************** estimate_numbers_of_iterations_loop (str
*** 1652,1664 ****
struct tree_niter_desc niter_desc;
/* Give up if we already have tried to compute an estimation. */
! if (loop->estimated_nb_iterations == chrec_dont_know
! /* Or when we already have an estimation. */
! || (loop->estimated_nb_iterations != NULL_TREE
! && TREE_CODE (loop->estimated_nb_iterations) == INTEGER_CST))
return;
! else
! loop->estimated_nb_iterations = chrec_dont_know;
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
--- 1812,1820 ----
struct tree_niter_desc niter_desc;
/* Give up if we already have tried to compute an estimation. */
! if (loop->estimated_nb_iterations != NULL_TREE)
return;
! loop->estimated_nb_iterations = chrec_dont_know;
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
*************** estimate_numbers_of_iterations_loop (str
*** 1668,1686 ****
niter = niter_desc.niter;
type = TREE_TYPE (niter);
! if (!zero_p (niter_desc.may_be_zero)
! && !nonzero_p (niter_desc.may_be_zero))
niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
build_int_cst (type, 0),
niter);
record_estimate (loop, niter,
niter_desc.additional_info,
! last_stmt (exits[i]->src));
}
free (exits);
! if (chrec_contains_undetermined (loop->estimated_nb_iterations))
! infer_loop_bounds_from_undefined (loop);
}
/* Records estimates on numbers of iterations of LOOPS. */
--- 1824,1842 ----
niter = niter_desc.niter;
type = TREE_TYPE (niter);
! if (TREE_CODE (niter_desc.may_be_zero) != INTEGER_CST)
niter = build3 (COND_EXPR, type, niter_desc.may_be_zero,
build_int_cst (type, 0),
niter);
record_estimate (loop, niter,
niter_desc.additional_info,
! last_stmt (exits[i]->src),
! true);
}
free (exits);
! infer_loop_bounds_from_undefined (loop);
! compute_estimated_nb_iterations (loop);
}
/* Records estimates on numbers of iterations of LOOPS. */
*************** stmt_dominates_stmt_p (tree s1, tree s2)
*** 1752,1791 ****
}
/* Returns true when we can prove that the number of executions of
! STMT in the loop is at most NITER, according to the fact
! that the statement NITER_BOUND->at_stmt is executed at most
! NITER_BOUND->bound times. */
static bool
n_of_executions_at_most (tree stmt,
struct nb_iter_bound *niter_bound,
tree niter)
{
! tree cond;
! tree bound = niter_bound->bound;
tree bound_type = TREE_TYPE (bound);
tree nit_type = TREE_TYPE (niter);
enum tree_code cmp;
gcc_assert (TYPE_UNSIGNED (bound_type)
&& TYPE_UNSIGNED (nit_type)
! && is_gimple_min_invariant (bound));
if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
! bound = fold_convert (nit_type, bound);
else
! niter = fold_convert (bound_type, niter);
! /* After the statement niter_bound->at_stmt we know that anything is
! executed at most BOUND times. */
! if (stmt && stmt_dominates_stmt_p (niter_bound->at_stmt, stmt))
! cmp = GE_EXPR;
! /* Before the statement niter_bound->at_stmt we know that anything
! is executed at most BOUND + 1 times. */
else
! cmp = GT_EXPR;
! cond = fold_binary (cmp, boolean_type_node, niter, bound);
! return nonzero_p (cond);
}
/* Checks whether it is correct to count the induction variable BASE +
--- 1908,1982 ----
}
/* Returns true when we can prove that the number of executions of
! STMT in the loop is at most NITER, according to the bound on
! the number of executions of the statement NITER_BOUND->stmt recorded in
! NITER_BOUND. If STMT is NULL, we must prove this bound for all
! statements in the loop. */
static bool
n_of_executions_at_most (tree stmt,
struct nb_iter_bound *niter_bound,
tree niter)
{
! tree bound = niter_bound->bound, max;
tree bound_type = TREE_TYPE (bound);
tree nit_type = TREE_TYPE (niter);
+ tree type;
enum tree_code cmp;
gcc_assert (TYPE_UNSIGNED (bound_type)
&& TYPE_UNSIGNED (nit_type)
! && TREE_CODE (bound) == INTEGER_CST);
if (TYPE_PRECISION (nit_type) > TYPE_PRECISION (bound_type))
! {
! type = nit_type;
! bound = fold_convert (nit_type, bound);
! }
else
! {
! type = bound_type;
! niter = fold_convert (bound_type, niter);
! }
! /* We know that NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
! times. This means that:
!
! -- if NITER_BOUND->is_exit is true, then everything before
! NITER_BOUND->stmt is executed at most NITER_BOUND->bound + 1
! times, and everyting after it at most NITER_BOUND->bound times.
!
! -- If NITER_BOUND->is_exit is false, then if we can prove that when STMT
! is executed, then NITER_BOUND->stmt is executed as well in the same
! iteration (we conclude that if both statements belong to the same
! basic block, or if STMT is after NITER_BOUND->stmt), then STMT
! is executed at most NITER_BOUND->bound + 1 times. Otherwise STMT is
! executed at most NITER_BOUND->bound + 2 times. */
!
! if (niter_bound->is_exit)
! {
! if (stmt
! && stmt != niter_bound->stmt
! && stmt_dominates_stmt_p (niter_bound->stmt, stmt))
! cmp = GE_EXPR;
! else
! cmp = GT_EXPR;
! }
else
! {
! if (!stmt
! || (bb_for_stmt (stmt) != bb_for_stmt (niter_bound->stmt)
! && !stmt_dominates_stmt_p (niter_bound->stmt, stmt)))
! {
! max = upper_bound_in_type (type, type);
! if (!tree_int_cst_lt (bound, max))
! return false;
! bound = fold_binary (PLUS_EXPR, type, bound, build_int_cst (type, 1));
! }
! cmp = GT_EXPR;
! }
!
! return nonzero_p (fold_binary (cmp, boolean_type_node, niter, bound));
}
/* Checks whether it is correct to count the induction variable BASE +
Index: tree-data-ref.c
===================================================================
*** tree-data-ref.c (revision 113549)
--- tree-data-ref.c (working copy)
*************** dump_ddrs (FILE *file, VEC (ddr_p, heap)
*** 834,908 ****
- /* Estimate the number of iterations from the size of the data and the
- access functions. */
-
- static void
- estimate_niter_from_size_of_data (struct loop *loop,
- tree opnd0,
- tree access_fn,
- tree stmt)
- {
- tree estimation = NULL_TREE;
- tree array_size, data_size, element_size;
- tree init, step;
-
- init = initial_condition (access_fn);
- step = evolution_part_in_loop_num (access_fn, loop->num);
-
- array_size = TYPE_SIZE (TREE_TYPE (opnd0));
- element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
- if (array_size == NULL_TREE
- || TREE_CODE (array_size) != INTEGER_CST
- || TREE_CODE (element_size) != INTEGER_CST)
- return;
-
- data_size = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
- array_size, element_size);
-
- if (init != NULL_TREE
- && step != NULL_TREE
- && TREE_CODE (init) == INTEGER_CST
- && TREE_CODE (step) == INTEGER_CST)
- {
- tree i_plus_s = fold_build2 (PLUS_EXPR, integer_type_node, init, step);
- tree sign = fold_binary (GT_EXPR, boolean_type_node, i_plus_s, init);
-
- if (sign == boolean_true_node)
- estimation = fold_build2 (CEIL_DIV_EXPR, integer_type_node,
- fold_build2 (MINUS_EXPR, integer_type_node,
- data_size, init), step);
-
- /* When the step is negative, as in PR23386: (init = 3, step =
- 0ffffffff, data_size = 100), we have to compute the
- estimation as ceil_div (init, 0 - step) + 1. */
- else if (sign == boolean_false_node)
- estimation =
- fold_build2 (PLUS_EXPR, integer_type_node,
- fold_build2 (CEIL_DIV_EXPR, integer_type_node,
- init,
- fold_build2 (MINUS_EXPR, unsigned_type_node,
- integer_zero_node, step)),
- integer_one_node);
-
- if (estimation)
- record_estimate (loop, estimation, boolean_true_node, stmt);
- }
- }
-
/* Given an ARRAY_REF node REF, records its access functions.
Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
i.e. the constant "3", then recursively call the function on opnd0,
i.e. the ARRAY_REF "A[i]".
- If ESTIMATE_ONLY is true, we just set the estimated number of loop
- iterations, we don't store the access function.
The function returns the base name: "A". */
static tree
analyze_array_indexes (struct loop *loop,
VEC(tree,heap) **access_fns,
! tree ref, tree stmt,
! bool estimate_only)
{
tree opnd0, opnd1;
tree access_fn;
--- 834,849 ----
/* Given an ARRAY_REF node REF, records its access functions.
Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
i.e. the constant "3", then recursively call the function on opnd0,
i.e. the ARRAY_REF "A[i]".
The function returns the base name: "A". */
static tree
analyze_array_indexes (struct loop *loop,
VEC(tree,heap) **access_fns,
! tree ref, tree stmt)
{
tree opnd0, opnd1;
tree access_fn;
*************** analyze_array_indexes (struct loop *loop
*** 917,948 ****
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
! if (estimate_only
! && chrec_contains_undetermined (loop->estimated_nb_iterations))
! estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
!
! if (!estimate_only)
! VEC_safe_push (tree, heap, *access_fns, access_fn);
/* Recursively record other array access functions. */
if (TREE_CODE (opnd0) == ARRAY_REF)
! return analyze_array_indexes (loop, access_fns, opnd0, stmt, estimate_only);
/* Return the base name of the data access. */
else
return opnd0;
}
- /* For an array reference REF contained in STMT, attempt to bound the
- number of iterations in the loop containing STMT */
-
- void
- estimate_iters_using_array (tree stmt, tree ref)
- {
- analyze_array_indexes (loop_containing_stmt (stmt), NULL, ref, stmt,
- true);
- }
-
/* For a data reference REF contained in the statement STMT, initialize
a DATA_REFERENCE structure, and return it. IS_READ flag has to be
set to true when REF is in the right hand side of an
--- 858,874 ----
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
! VEC_safe_push (tree, heap, *access_fns, access_fn);
/* Recursively record other array access functions. */
if (TREE_CODE (opnd0) == ARRAY_REF)
! return analyze_array_indexes (loop, access_fns, opnd0, stmt);
/* Return the base name of the data access. */
else
return opnd0;
}
/* For a data reference REF contained in the statement STMT, initialize
a DATA_REFERENCE structure, and return it. IS_READ flag has to be
set to true when REF is in the right hand side of an
*************** analyze_array (tree stmt, tree ref, bool
*** 968,974 ****
DR_REF (res) = ref;
acc_fns = VEC_alloc (tree, heap, 3);
DR_BASE_OBJECT (res) = analyze_array_indexes
! (loop_containing_stmt (stmt), &acc_fns, ref, stmt, false);
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, acc_fns);
DR_IS_READ (res) = is_read;
--- 894,900 ----
DR_REF (res) = ref;
acc_fns = VEC_alloc (tree, heap, 3);
DR_BASE_OBJECT (res) = analyze_array_indexes
! (loop_containing_stmt (stmt), &acc_fns, ref, stmt);
DR_TYPE (res) = ARRAY_REF_TYPE;
DR_SET_ACCESS_FNS (res, acc_fns);
DR_IS_READ (res) = is_read;
Index: tree-data-ref.h
===================================================================
*** tree-data-ref.h (revision 113549)
--- tree-data-ref.h (working copy)
*************** extern void free_dependence_relation (st
*** 292,298 ****
extern void free_dependence_relations (VEC (ddr_p, heap) *);
extern void free_data_refs (VEC (data_reference_p, heap) *);
extern struct data_reference *analyze_array (tree, tree, bool);
- extern void estimate_iters_using_array (tree, tree);
/* Return the index of the variable VAR in the LOOP_NEST array. */
--- 292,297 ----
Index: cfgloop.h
===================================================================
*** cfgloop.h (revision 113549)
--- cfgloop.h (working copy)
*************** struct lpt_decision
*** 47,58 ****
struct nb_iter_bound
{
! tree bound; /* The constant expression whose value is an upper
! bound on the number of executions of ... */
! tree at_stmt; /* ... this statement during one execution of
! a loop. */
struct nb_iter_bound *next;
- /* The next bound in a list. */
};
/* Structure to hold information for each natural loop. */
--- 47,71 ----
struct nb_iter_bound
{
! /* The statement STMT is executed at most ... */
! tree stmt;
!
! /* ... BOUND + 1 times (BOUND must be an unsigned constant).
! The + 1 is added for the following reasons:
!
! a) 0 would otherwise be unused, while we would need to care more about
! overflows (as MAX + 1 is sometimes produced as the estimate on number
! of executions of STMT).
! b) it is consistent with the result of number_of_iterations_exit. */
! tree bound;
!
! /* True if the statement will cause the loop to be leaved the (at most)
! BOUND + 1-st time it is executed, that is, all the statements after it
! are executed at most BOUND times. */
! bool is_exit;
!
! /* The next bound in the list. */
struct nb_iter_bound *next;
};
/* Structure to hold information for each natural loop. */
*************** enum
*** 398,403 ****
extern void unroll_and_peel_loops (struct loops *, int);
extern void doloop_optimize_loops (struct loops *);
extern void move_loop_invariants (struct loops *);
- extern void record_estimate (struct loop *, tree, tree, tree);
#endif /* GCC_CFGLOOP_H */
--- 411,415 ----