This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Cleanup # of iteration estimation infrastructure
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 10 Nov 2006 00:27:26 +0100
- Subject: [patch] Cleanup # of iteration estimation infrastructure
Hello,
this patch is basically updated
http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00290.html. It splits the
code for deriving and recording bounds on number of iterations into
several new functions, and moves all the knowledge necessary to
determine the bound to single place -- record_nonwrapping_iv function.
The main change with respect to the old version is that it now uses
double_int for recording the bounds.
We also record whether the estimate is "realistic" -- i.e., whether it
is likely that the number of iterations is close to the upper bound.
This is useful e.g. for the heuristics in linear loop transformations,
to decide whether to take the number of iterations estimated from these
bounds into account or not.
Bootstrapped & regtested on i686.
Zdenek
* Makefile.in (tree-data-ref.o): Add langhooks.h dependency.
* tree-ssa-loop-niter.c (derive_constant_upper_bound): Follow
ud-chains. Handle AND_EXPR.
(record_estimate): Record whether the estimate is realistic
and whether it is derived from a loop exit.
(record_nonwrapping_iv, idx_infer_loop_bounds, infer_loop_bounds_from_ref,
infer_loop_bounds_from_array, infer_loop_bounds_from_signedness): New
functions.
(compute_estimated_nb_iterations): Take only realistic bounds into
account. Set estimate_state. Use double_ints.
(infer_loop_bounds_from_undefined): Call infer_loop_bounds_from_array
and infer_loop_bounds_from_signedness. Do not consider basic blocks
that do not have to be always executed.
(estimate_numbers_of_iterations_loop): Set estimate_state, and use it
to determine whether to call infer_loop_bounds_from_undefined
and compute_estimated_nb_iterations.
(n_of_executions_at_most): Use double_ints.
(free_numbers_of_iterations_estimates_loop): Set estimate_state.
(substitute_in_loop_info): Do not replace in estimated_nb_iterations.
* double-int.c (double_int_to_tree): Improve comment.
(double_int_fits_to_tree_p): New function.
* double-int.h (double_int_fits_to_tree_p): Declare.
* tree-data-ref.c: Include langhooks.h.
(estimate_niter_from_size_of_data, estimate_iters_using_array): Removed.
(analyze_array_indexes): Do not call estimate_niter_from_size_of_data.
(analyze_array): Do not pass estimate_only argument to
analyze_array_indexes.
(get_number_of_iters_for_loop): Build tree from the stored double_int
value.
(get_references_in_stmt, find_data_references_in_stmt): New functions.
(find_data_references_in_loop): Use find_data_references_in_stmt.
* tree-data-ref.h (struct data_ref_loc_d): New.
(get_references_in_stmt): Declare.
(estimate_iters_using_array): Declaration removed.
* cfgloop.h (struct nb_iter_bound): Change type of bound to
double_int. Improve comments. Add is_exit and realistic
fields.
(struct loop): Changed type of estimated_nb_iterations to double_int.
Added estimate_state field.
(record_estimate): Declaration removed.
Index: Makefile.in
===================================================================
*** Makefile.in (revision 118601)
--- Makefile.in (working copy)
*************** tree-scalar-evolution.o: tree-scalar-evo
*** 2080,2086 ****
tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
! $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h
tree-vect-analyze.o: tree-vect-analyze.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(BASIC_BLOCK_H) \
$(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
--- 2084,2090 ----
tree-data-ref.o: tree-data-ref.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(GGC_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \
$(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
! $(TREE_DATA_REF_H) $(SCEV_H) tree-pass.h tree-chrec.h langhooks.h
tree-vect-analyze.o: tree-vect-analyze.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
$(TM_H) $(GGC_H) $(OPTABS_H) $(TREE_H) $(BASIC_BLOCK_H) \
$(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
Index: tree-ssa-loop-niter.c
===================================================================
*** tree-ssa-loop-niter.c (revision 118545)
--- tree-ssa-loop-niter.c (working copy)
*************** derive_constant_upper_bound (tree val, t
*** 1533,1538 ****
--- 1533,1539 ----
tree type = TREE_TYPE (val);
tree op0, op1, subtype, maxt;
double_int bnd, max, mmax, cst;
+ tree stmt;
if (INTEGRAL_TYPE_P (type))
maxt = TYPE_MAX_VALUE (type);
*************** derive_constant_upper_bound (tree val, t
*** 1647,1685 ****
bnd = derive_constant_upper_bound (op0, additional);
return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
default:
return max;
}
}
! /* 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));
double_int i_bound = derive_constant_upper_bound (bound, additional);
- tree c_bound = double_int_to_tree (unsigned_type_for (TREE_TYPE (bound)),
- i_bound);
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. */
--- 1648,1760 ----
bnd = derive_constant_upper_bound (op0, additional);
return double_int_udiv (bnd, tree_to_double_int (op1), FLOOR_DIV_EXPR);
+ case BIT_AND_EXPR:
+ op1 = TREE_OPERAND (val, 1);
+ if (TREE_CODE (op1) != INTEGER_CST
+ || tree_int_cst_sign_bit (op1))
+ return max;
+ return tree_to_double_int (op1);
+
+ case SSA_NAME:
+ stmt = SSA_NAME_DEF_STMT (val);
+ if (TREE_CODE (stmt) != MODIFY_EXPR
+ || TREE_OPERAND (stmt, 0) != val)
+ return max;
+ return derive_constant_upper_bound (TREE_OPERAND (stmt, 1), additional);
+
default:
return max;
}
}
! /* 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.
! REALISTIC is true if the estimate comes from a reliable source
! (number of iterations analysis, or size of data accessed in the loop). */
! static void
! record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt,
! bool is_exit, bool realistic)
{
struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
double_int i_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 ");
! dump_double_int (dump_file, i_bound, true);
! fprintf (dump_file, ") + 1 times in loop %d.\n", loop->num);
}
! elt->bound = i_bound;
! elt->stmt = at_stmt;
! elt->is_exit = is_exit;
! elt->realistic = realistic && TREE_CODE (bound) == INTEGER_CST;
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>. DATA_SIZE_BOUNDS_P is true if
+ LOW and HIGH are derived from the size of data. */
+
+ static void
+ record_nonwrapping_iv (struct loop *loop, tree base, tree step, tree stmt,
+ tree low, tree high, bool data_size_bounds_p)
+ {
+ 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);
+ if (TREE_CODE (base) != INTEGER_CST)
+ base = fold_convert (unsigned_type, high);
+ delta = fold_build2 (MINUS_EXPR, unsigned_type, base, extreme);
+ step = fold_build1 (NEGATE_EXPR, unsigned_type, step);
+ }
+ else
+ {
+ extreme = fold_convert (unsigned_type, high);
+ if (TREE_CODE (base) != INTEGER_CST)
+ base = fold_convert (unsigned_type, low);
+ delta = fold_build2 (MINUS_EXPR, unsigned_type, extreme, base);
+ }
+
+ /* 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, boolean_true_node, stmt,
+ false, data_size_bounds_p);
+ }
+
/* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
approximation of the number of iterations for LOOP. */
*************** static void
*** 1687,1706 ****
compute_estimated_nb_iterations (struct loop *loop)
{
struct nb_iter_bound *bound;
!
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. */
! if (chrec_contains_undetermined (loop->estimated_nb_iterations)
! || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations))
! loop->estimated_nb_iterations = bound->bound;
}
}
/* The following analyzers are extracting informations on the bounds
of LOOP from the following undefined behaviors:
--- 1762,1945 ----
compute_estimated_nb_iterations (struct loop *loop)
{
struct nb_iter_bound *bound;
!
! gcc_assert (loop->estimate_state == EST_NOT_AVAILABLE);
!
for (bound = loop->bounds; bound; bound = bound->next)
{
! if (!bound->realistic)
continue;
/* Update only when there is no previous estimation, or when the current
estimation is smaller. */
! if (loop->estimate_state == EST_NOT_AVAILABLE
! || double_int_ucmp (bound->bound, loop->estimated_nb_iterations) < 0)
! {
! loop->estimate_state = EST_AVAILABLE;
! loop->estimated_nb_iterations = bound->bound;
! }
! }
! }
!
! /* 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, true);
! 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, false);
+ }
+
/* The following analyzers are extracting informations on the bounds
of LOOP from the following undefined behaviors:
*************** static void
*** 1714,1721 ****
infer_loop_bounds_from_undefined (struct loop *loop)
{
unsigned i;
! basic_block bb, *bbs;
block_stmt_iterator bsi;
bbs = get_loop_body (loop);
--- 1953,1961 ----
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
*** 1723,1817 ****
{
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);
!
! 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;
!
! if (integer_nonzerop (step))
! {
! tree utype;
!
! if (tree_int_cst_lt (step, integer_zero_node))
! diff = fold_build2 (MINUS_EXPR, type, init,
! TYPE_MIN_VALUE (type));
! else
! diff = fold_build2 (MINUS_EXPR, type,
! TYPE_MAX_VALUE (type), init);
!
! utype = unsigned_type_for (type);
! estimation = fold_build2 (CEIL_DIV_EXPR, type, diff,
! step);
! record_estimate (loop,
! fold_convert (utype, 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);
}
--- 1963,1983 ----
{
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
*** 1826,1838 ****
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++)
--- 1992,2000 ----
struct tree_niter_desc niter_desc;
/* Give up if we already have tried to compute an estimation. */
! if (loop->estimate_state != EST_NOT_COMPUTED)
return;
! loop->estimate_state = EST_NOT_AVAILABLE;
exits = get_loop_exit_edges (loop, &n_exits);
for (i = 0; i < n_exits; i++)
*************** estimate_numbers_of_iterations_loop (str
*** 1842,1860 ****
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. */
--- 2004,2022 ----
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, 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)
*** 1899,1938 ****
}
/* 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);
}
/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
--- 2061,2127 ----
}
/* 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)
{
! double_int bound = niter_bound->bound;
tree nit_type = TREE_TYPE (niter);
enum tree_code cmp;
! gcc_assert (TYPE_UNSIGNED (nit_type));
!
! /* If the bound does not even fit into NIT_TYPE, it cannot tell us that
! the number of iterations is small. */
! if (!double_int_fits_to_tree_p (nit_type, bound))
! return false;
! /* 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)))
! {
! bound = double_int_add (bound, double_int_one);
! if (double_int_zero_p (bound)
! || !double_int_fits_to_tree_p (nit_type, bound))
! return false;
! }
! cmp = GT_EXPR;
! }
! return nonzero_p (fold_binary (cmp, boolean_type_node,
! niter,
! double_int_to_tree (nit_type, bound)));
}
/* Returns true if the arithmetics in TYPE can be assumed not to wrap. */
*************** free_numbers_of_iterations_estimates_loo
*** 2042,2048 ****
struct nb_iter_bound *bound, *next;
loop->nb_iterations = NULL;
! loop->estimated_nb_iterations = NULL;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
--- 2231,2237 ----
struct nb_iter_bound *bound, *next;
loop->nb_iterations = NULL;
! loop->estimate_state = EST_NOT_COMPUTED;
for (bound = loop->bounds; bound; bound = next)
{
next = bound->next;
*************** void
*** 2075,2080 ****
substitute_in_loop_info (struct loop *loop, tree name, tree val)
{
loop->nb_iterations = simplify_replace_tree (loop->nb_iterations, name, val);
- loop->estimated_nb_iterations
- = simplify_replace_tree (loop->estimated_nb_iterations, name, val);
}
--- 2264,2267 ----
Index: double-int.c
===================================================================
*** double-int.c (revision 118545)
--- double-int.c (working copy)
*************** double_int_umod (double_int a, double_in
*** 290,296 ****
return double_int_mod (a, b, true, code);
}
! /* Constructs tree in type TYPE from with value given by CST. */
tree
double_int_to_tree (tree type, double_int cst)
--- 290,297 ----
return double_int_mod (a, b, true, code);
}
! /* Constructs tree in type TYPE from with value given by CST. Signedness of CST
! is assumed to be the same as the signedness of TYPE. */
tree
double_int_to_tree (tree type, double_int cst)
*************** double_int_to_tree (tree type, double_in
*** 300,305 ****
--- 301,319 ----
return build_int_cst_wide (type, cst.low, cst.high);
}
+ /* Returns true if CST fits into range of TYPE. Signedness of CST is assumed
+ to be the same as the signedness of TYPE. */
+
+ bool
+ double_int_fits_to_tree_p (tree type, double_int cst)
+ {
+ double_int ext = double_int_ext (cst,
+ TYPE_PRECISION (type),
+ TYPE_UNSIGNED (type));
+
+ return double_int_equal_p (cst, ext);
+ }
+
/* Returns true if CST is negative. Of course, CST is considered to
be signed. */
Index: double-int.h
===================================================================
*** double-int.h (revision 118545)
--- double-int.h (working copy)
*************** union tree_node;
*** 58,64 ****
/* Constructors and conversions. */
union tree_node *double_int_to_tree (union tree_node *, double_int);
! double_int tree_to_double_int (union tree_node *tree);
/* Constructs double_int from integer CST. The bits over the precision of
HOST_WIDE_INT are filled with the sign bit. */
--- 58,65 ----
/* Constructors and conversions. */
union tree_node *double_int_to_tree (union tree_node *, double_int);
! bool double_int_fits_to_tree_p (union tree_node *, double_int);
! double_int tree_to_double_int (union tree_node *);
/* Constructs double_int from integer CST. The bits over the precision of
HOST_WIDE_INT are filled with the sign bit. */
Index: tree-data-ref.c
===================================================================
*** tree-data-ref.c (revision 118545)
--- tree-data-ref.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 93,98 ****
--- 93,99 ----
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
+ #include "langhooks.h"
static struct datadep_stats
{
*************** dump_ddrs (FILE *file, VEC (ddr_p, heap)
*** 888,962 ****
- /* 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;
--- 889,904 ----
/* 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
*** 971,1002 ****
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
--- 913,929 ----
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
*** 1022,1028 ****
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;
--- 949,955 ----
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;
*************** analyze_ziv_subscript (tree chrec_a,
*** 2377,2389 ****
static tree
get_number_of_iters_for_loop (int loopnum)
{
! tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
! if (TREE_CODE (numiter) != INTEGER_CST)
! numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
! if (chrec_contains_undetermined (numiter))
! return NULL_TREE;
! return numiter;
}
/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
--- 2304,2323 ----
static tree
get_number_of_iters_for_loop (int loopnum)
{
! struct loop *loop = current_loops->parray[loopnum];
! tree numiter = number_of_iterations_in_loop (loop);
!
! if (TREE_CODE (numiter) == INTEGER_CST)
! return numiter;
!
! if (loop->estimate_state == EST_AVAILABLE)
! {
! tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
! if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
! return double_int_to_tree (type, loop->estimated_nb_iterations);
! }
! return NULL_TREE;
}
/* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
*************** compute_all_dependences (VEC (data_refer
*** 4060,4065 ****
--- 3994,4098 ----
}
}
+ /* Stores the locations of memory references in STMT to REFERENCES. Returns
+ true if STMT clobbers memory, false otherwise. */
+
+ bool
+ get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
+ {
+ bool clobbers_memory = false;
+ data_ref_loc *ref;
+ tree *op0, *op1, args, call;
+
+ *references = NULL;
+
+ /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
+ Calls have side-effects, except those to const or pure
+ functions. */
+ call = get_call_expr_in (stmt);
+ if ((call
+ && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
+ || (TREE_CODE (stmt) == ASM_EXPR
+ && ASM_VOLATILE_P (stmt)))
+ clobbers_memory = true;
+
+ if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
+ return clobbers_memory;
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ op0 = &TREE_OPERAND (stmt, 0);
+ op1 = &TREE_OPERAND (stmt, 1);
+
+ if (DECL_P (*op1)
+ || REFERENCE_CLASS_P (*op1))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op1;
+ ref->is_read = true;
+ }
+
+ if (DECL_P (*op0)
+ || REFERENCE_CLASS_P (*op0))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op0;
+ ref->is_read = false;
+ }
+ }
+
+ if (call)
+ {
+ for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
+ {
+ op0 = &TREE_VALUE (args);
+ if (DECL_P (*op0)
+ || REFERENCE_CLASS_P (*op0))
+ {
+ ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
+ ref->pos = op0;
+ ref->is_read = true;
+ }
+ }
+ }
+
+ return clobbers_memory;
+ }
+
+ /* Stores the data references in STMT to DATAREFS. If there is an unanalyzable
+ reference, returns false, otherwise returns true. */
+
+ static bool
+ find_data_references_in_stmt (tree stmt,
+ VEC (data_reference_p, heap) **datarefs)
+ {
+ unsigned i;
+ VEC (data_ref_loc, heap) *references;
+ data_ref_loc *ref;
+ bool ret = true;
+ data_reference_p dr;
+
+ if (get_references_in_stmt (stmt, &references))
+ {
+ VEC_free (data_ref_loc, heap, references);
+ return false;
+ }
+
+ for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
+ {
+ dr = create_data_ref (*ref->pos, stmt, ref->is_read);
+ if (dr)
+ VEC_safe_push (data_reference_p, heap, *datarefs, dr);
+ else
+ {
+ ret = false;
+ break;
+ }
+ }
+ VEC_free (data_ref_loc, heap, references);
+ return ret;
+ }
+
/* Search the data references in LOOP, and record the information into
DATAREFS. Returns chrec_dont_know when failing to analyze a
difficult case, returns NULL_TREE otherwise.
*************** find_data_references_in_loop (struct loo
*** 4074,4191 ****
basic_block bb, *bbs;
unsigned int i;
block_stmt_iterator bsi;
- struct data_reference *dr;
bbs = get_loop_body (loop);
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! {
tree stmt = bsi_stmt (bsi);
! /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
! Calls have side-effects, except those to const or pure
! functions. */
! if ((TREE_CODE (stmt) == CALL_EXPR
! && !(call_expr_flags (stmt) & (ECF_CONST | ECF_PURE)))
! || (TREE_CODE (stmt) == ASM_EXPR
! && ASM_VOLATILE_P (stmt)))
! goto insert_dont_know_node;
!
! if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
! continue;
!
! switch (TREE_CODE (stmt))
{
! case MODIFY_EXPR:
! {
! bool one_inserted = false;
! tree opnd0 = TREE_OPERAND (stmt, 0);
! tree opnd1 = TREE_OPERAND (stmt, 1);
!
! if (TREE_CODE (opnd0) == ARRAY_REF
! || TREE_CODE (opnd0) == INDIRECT_REF
! || TREE_CODE (opnd0) == COMPONENT_REF)
! {
! dr = create_data_ref (opnd0, stmt, false);
! if (dr)
! {
! VEC_safe_push (data_reference_p, heap, *datarefs, dr);
! one_inserted = true;
! }
! }
!
! if (TREE_CODE (opnd1) == ARRAY_REF
! || TREE_CODE (opnd1) == INDIRECT_REF
! || TREE_CODE (opnd1) == COMPONENT_REF)
! {
! dr = create_data_ref (opnd1, stmt, true);
! if (dr)
! {
! VEC_safe_push (data_reference_p, heap, *datarefs, dr);
! one_inserted = true;
! }
! }
!
! if (!one_inserted)
! goto insert_dont_know_node;
!
! break;
! }
!
! case CALL_EXPR:
! {
! tree args;
! bool one_inserted = false;
!
! for (args = TREE_OPERAND (stmt, 1); args;
! args = TREE_CHAIN (args))
! if (TREE_CODE (TREE_VALUE (args)) == ARRAY_REF
! || TREE_CODE (TREE_VALUE (args)) == INDIRECT_REF
! || TREE_CODE (TREE_VALUE (args)) == COMPONENT_REF)
! {
! dr = create_data_ref (TREE_VALUE (args), stmt, true);
! if (dr)
! {
! VEC_safe_push (data_reference_p, heap, *datarefs, dr);
! one_inserted = true;
! }
! }
!
! if (!one_inserted)
! goto insert_dont_know_node;
!
! break;
! }
! default:
! {
! struct data_reference *res;
!
! insert_dont_know_node:;
! res = XNEW (struct data_reference);
! DR_STMT (res) = NULL_TREE;
! DR_REF (res) = NULL_TREE;
! DR_BASE_OBJECT (res) = NULL;
! DR_TYPE (res) = ARRAY_REF_TYPE;
! DR_SET_ACCESS_FNS (res, NULL);
! DR_BASE_OBJECT (res) = NULL;
! DR_IS_READ (res) = false;
! DR_BASE_ADDRESS (res) = NULL_TREE;
! DR_OFFSET (res) = NULL_TREE;
! DR_INIT (res) = NULL_TREE;
! DR_STEP (res) = NULL_TREE;
! DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
! DR_MEMTAG (res) = NULL_TREE;
! DR_PTR_INFO (res) = NULL;
! VEC_safe_push (data_reference_p, heap, *datarefs, res);
!
! free (bbs);
! return chrec_dont_know;
! }
}
/* When there are no defs in the loop, the loop is parallel. */
--- 4107,4147 ----
basic_block bb, *bbs;
unsigned int i;
block_stmt_iterator bsi;
bbs = get_loop_body (loop);
+ loop->parallel_p = true;
for (i = 0; i < loop->num_nodes; i++)
{
bb = bbs[i];
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
! {
tree stmt = bsi_stmt (bsi);
! if (!find_data_references_in_stmt (stmt, datarefs))
{
! struct data_reference *res;
! res = XNEW (struct data_reference);
! DR_STMT (res) = NULL_TREE;
! DR_REF (res) = NULL_TREE;
! DR_BASE_OBJECT (res) = NULL;
! DR_TYPE (res) = ARRAY_REF_TYPE;
! DR_SET_ACCESS_FNS (res, NULL);
! DR_BASE_OBJECT (res) = NULL;
! DR_IS_READ (res) = false;
! DR_BASE_ADDRESS (res) = NULL_TREE;
! DR_OFFSET (res) = NULL_TREE;
! DR_INIT (res) = NULL_TREE;
! DR_STEP (res) = NULL_TREE;
! DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
! DR_MEMTAG (res) = NULL_TREE;
! DR_PTR_INFO (res) = NULL;
! loop->parallel_p = false;
! VEC_safe_push (data_reference_p, heap, *datarefs, res);
! free (bbs);
! return chrec_dont_know;
}
/* When there are no defs in the loop, the loop is parallel. */
*************** find_data_references_in_loop (struct loo
*** 4193,4199 ****
loop->parallel_p = false;
}
}
-
free (bbs);
return NULL_TREE;
--- 4149,4154 ----
Index: tree-data-ref.h
===================================================================
*** tree-data-ref.h (revision 118545)
--- tree-data-ref.h (working copy)
*************** DEF_VEC_ALLOC_P(ddr_p,heap);
*** 269,274 ****
--- 269,289 ----
+ /* Describes a location of a memory reference. */
+
+ typedef struct data_ref_loc_d
+ {
+ /* Position of the memory reference. */
+ tree *pos;
+
+ /* True if the memory reference is read. */
+ bool is_read;
+ } data_ref_loc;
+
+ DEF_VEC_O (data_ref_loc);
+ DEF_VEC_ALLOC_O (data_ref_loc, heap);
+
+ bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
extern tree find_data_references_in_loop (struct loop *,
VEC (data_reference_p, heap) **);
extern void compute_data_dependences_for_loop (struct loop *, bool,
*************** 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. */
--- 307,312 ----
Index: cfgloop.h
===================================================================
*** cfgloop.h (revision 118545)
--- 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,77 ----
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. */
! double_int 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;
!
! /* True if the bound is "realistic" -- i.e., most likely the loop really has
! number of iterations close to the bound. Exact bounds (if the number of
! iterations of a loop is a constant) and bounds derived from the size of
! data accessed in the loop are considered realistic. */
! bool realistic;
!
! /* The next bound in the list. */
struct nb_iter_bound *next;
};
/* Structure to hold information for each natural loop. */
*************** struct loop
*** 111,119 ****
information in this field. */
tree nb_iterations;
! /* An INTEGER_CST estimation of the number of iterations. NULL_TREE
! if there is no estimation. */
! tree estimated_nb_iterations;
/* Upper bound on number of iterations of a loop. */
struct nb_iter_bound *bounds;
--- 130,147 ----
information in this field. */
tree nb_iterations;
! /* An integer estimation of the number of iterations. Estimate_state
! describes what is the state of the estimation. */
! enum
! {
! /* Estimate was not computed yet. */
! EST_NOT_COMPUTED,
! /* Estimate was computed, but we could derive no useful bound. */
! EST_NOT_AVAILABLE,
! /* Estimate is ready. */
! EST_AVAILABLE
! } estimate_state;
! double_int estimated_nb_iterations;
/* Upper bound on number of iterations of a loop. */
struct nb_iter_bound *bounds;
*************** 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 */
--- 426,430 ----