This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch] Improve chrec_convert PR/21861 and PR/18403
Okay,
here is the patch for computing the estimation of niter on demand.
Bootstrapped and tested on amd64-linux, committed.
Sebastian
* tree-data-ref.c (compute_estimated_nb_iterations,
analyze_array_indexes, compute_overlap_steps_for_affine_1_2,
analyze_subscript_affine_affine, find_data_references_in_loop):
Fixed to use chrec_contains_undetermined to test the values of
loop->estimated_nb_iterations.
* tree-ssa-loop-niter.c (estimate_numbers_of_iterations_loop):
Compute the estimation only when loop->estimated_nb_iterations
has not yet been initialized.
(convert_step_widening, scev_probably_wraps_p): Add a call to
estimate_numbers_of_iterations_loop.
* tree-vrp.c (execute_vrp): Don't call estimate_numbers_of_iterations.
Index: tree-data-ref.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-data-ref.c,v
retrieving revision 2.31
diff -c -3 -p -r2.31 tree-data-ref.c
*** tree-data-ref.c 3 Jun 2005 23:27:03 -0000 2.31
--- tree-data-ref.c 8 Jun 2005 08:26:52 -0000
*************** dump_ddrs (FILE *file, varray_type ddrs)
*** 447,478 ****
! /* Compute the lowest iteration bound for LOOP. It is an
! INTEGER_CST. */
static void
compute_estimated_nb_iterations (struct loop *loop)
{
! tree estimation;
! struct nb_iter_bound *bound, *next;
! for (bound = loop->bounds; bound; bound = next)
! {
! next = bound->next;
! estimation = bound->bound;
!
! if (TREE_CODE (estimation) != INTEGER_CST)
! continue;
!
! if (loop->estimated_nb_iterations)
! {
! /* Update only if estimation is smaller. */
! if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
! loop->estimated_nb_iterations = estimation;
! }
! else
! loop->estimated_nb_iterations = estimation;
! }
}
/* Estimate the number of iterations from the size of the data and the
--- 447,467 ----
! /* Initialize LOOP->ESTIMATED_NB_ITERATIONS with the lowest safe
! approximation of the number of iterations for LOOP. */
static void
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
! /* Update only when there is no previous estimation. */
! && (chrec_contains_undetermined (loop->estimated_nb_iterations)
! /* Or when the current estimation is smaller. */
! || tree_int_cst_lt (bound->bound, loop->estimated_nb_iterations)))
! loop->estimated_nb_iterations = bound->bound;
}
/* Estimate the number of iterations from the size of the data and the
*************** analyze_array_indexes (struct loop *loop
*** 538,544 ****
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
! if (loop->estimated_nb_iterations == NULL_TREE)
estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
VEC_safe_push (tree, heap, *access_fns, access_fn);
--- 527,533 ----
access_fn = instantiate_parameters
(loop, analyze_scalar_evolution (loop, opnd1));
! if (chrec_contains_undetermined (loop->estimated_nb_iterations))
estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
VEC_safe_push (tree, heap, *access_fns, access_fn);
*************** compute_overlap_steps_for_affine_1_2 (tr
*** 1129,1136 ****
numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
! if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
! || numiter_z == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
--- 1118,1129 ----
numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
! if (chrec_contains_undetermined (numiter_x)
! || chrec_contains_undetermined (numiter_y)
! || chrec_contains_undetermined (numiter_z)
! || TREE_CODE (numiter_x) != INTEGER_CST
! || TREE_CODE (numiter_y) != INTEGER_CST
! || TREE_CODE (numiter_z) != INTEGER_CST)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*************** analyze_subscript_affine_affine (tree ch
*** 1278,1284 ****
if (TREE_CODE (numiter_b) != INTEGER_CST)
numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
! if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
--- 1271,1280 ----
if (TREE_CODE (numiter_b) != INTEGER_CST)
numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
! if (chrec_contains_undetermined (numiter_a)
! || chrec_contains_undetermined (numiter_b)
! || TREE_CODE (numiter_a) != INTEGER_CST
! || TREE_CODE (numiter_b) != INTEGER_CST)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*************** analyze_subscript_affine_affine (tree ch
*** 1379,1385 ****
if (TREE_CODE (numiter_b) != INTEGER_CST)
numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
! if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
--- 1375,1384 ----
if (TREE_CODE (numiter_b) != INTEGER_CST)
numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
->estimated_nb_iterations;
! if (chrec_contains_undetermined (numiter_a)
! || chrec_contains_undetermined (numiter_b)
! || TREE_CODE (numiter_a) != INTEGER_CST
! || TREE_CODE (numiter_b) != INTEGER_CST)
{
*overlaps_a = chrec_dont_know;
*overlaps_b = chrec_dont_know;
*************** find_data_references_in_loop (struct loo
*** 2344,2354 ****
/* When there are no defs in the loop, the loop is parallel. */
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
! bb->loop_father->parallel_p = false;
}
! if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
! compute_estimated_nb_iterations (bb->loop_father);
}
free (bbs);
--- 2343,2353 ----
/* When there are no defs in the loop, the loop is parallel. */
if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
! loop->parallel_p = false;
}
! if (chrec_contains_undetermined (loop->estimated_nb_iterations))
! compute_estimated_nb_iterations (loop);
}
free (bbs);
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.29
diff -c -3 -p -r2.29 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 7 Jun 2005 19:51:24 -0000 2.29
--- tree-ssa-loop-niter.c 8 Jun 2005 08:26:52 -0000
*************** estimate_numbers_of_iterations_loop (str
*** 1348,1353 ****
--- 1348,1362 ----
unsigned i, n_exits;
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++)
{
*************** estimate_numbers_of_iterations_loop (str
*** 1368,1374 ****
free (exits);
/* Analyzes the bounds of arrays accessed in the loop. */
! if (loop->estimated_nb_iterations == NULL_TREE)
{
varray_type datarefs;
VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
--- 1377,1383 ----
free (exits);
/* Analyzes the bounds of arrays accessed in the loop. */
! if (chrec_contains_undetermined (loop->estimated_nb_iterations))
{
varray_type datarefs;
VARRAY_GENERIC_PTR_INIT (datarefs, 3, "datarefs");
*************** convert_step_widening (struct loop *loop
*** 1581,1586 ****
--- 1590,1596 ----
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type,
delta, step_abs);
+ estimate_numbers_of_iterations_loop (loop);
for (bound = loop->bounds; bound; bound = bound->next)
if (proved_non_wrapping_p (at_stmt, bound, new_type, valid_niter))
return step_in_new_type;
*************** scev_probably_wraps_p (tree type, tree b
*** 1649,1654 ****
--- 1659,1665 ----
step_abs = fold_convert (unsigned_type, step_abs);
valid_niter = fold_build2 (FLOOR_DIV_EXPR, unsigned_type, delta, step_abs);
+ estimate_numbers_of_iterations_loop (loop);
for (bound = loop->bounds; bound; bound = bound->next)
if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter))
return false;
Index: tree-vrp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-vrp.c,v
retrieving revision 2.24
diff -c -3 -p -r2.24 tree-vrp.c
*** tree-vrp.c 7 Jun 2005 19:51:25 -0000 2.24
--- tree-vrp.c 8 Jun 2005 08:26:56 -0000
*************** execute_vrp (void)
*** 3509,3518 ****
cfg_loops = loop_optimizer_init (NULL);
if (cfg_loops)
! {
! scev_initialize (cfg_loops);
! estimate_numbers_of_iterations (cfg_loops);
! }
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
--- 3509,3515 ----
cfg_loops = loop_optimizer_init (NULL);
if (cfg_loops)
! scev_initialize (cfg_loops);
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);