This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Reduce number of # iterations queries
- From: Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sat, 2 Oct 2004 14:56:48 +0200
- Subject: [patch] Reduce number of # iterations queries
Hello,
this patch tries to reduce the number of # of iterations queries (that
got increased a lot due to iv elimination improvement I commited a few
days ago), by caching the results. This is important since # of
iterations analysis tends to produce a lot of unshared integer constants
and this showed up quite significantly in the amount of garbage
produced.
The patch should also decrease number of find_loop_niter_by_eval calls.
So far we were prefering the number of iterations obtained by more
mundane means (scev) only for loops with single exit; this patch makes
us take scev results into account also for loops with more exits.
Bootstrapped & regtested on ia64.
Zdenek
* tree-flow.h (find_loop_niter): Declare.
* tree-ssa-loop-ivcanon.c (canonicalize_loop_induction_variables):
Try using scev even for loops with more than one exit.
* tree-ssa-loop-ivopts.c (struct loop_data): Removed niter field.
(struct ivopts_data): Added niters field.
(struct nfe_cache_elt): New.
(nfe_hash, nfe_eq, niter_for_exit, niter_for_single_dom_exit): New
functions.
(tree_ssa_iv_optimize_init): Initialize niters cache.
(determine_number_of_iterations): Removed.
(find_induction_variables): Do not call determine_number_of_iterations.
Access niters for single exit through niter_for_single_dom_exit.
(add_iv_outer_candidates): Access niters for single exit through
niter_for_single_dom_exit.
(may_eliminate_iv): Take data argument. Use niter_for_exit.
(determine_use_iv_cost_condition): Pass data to may_eliminate_iv.
(may_replace_final_value): Take data argument. Use
niter_for_single_dom_exit.
(determine_use_iv_cost_outer): Pass data to may_replace_final_value.
(rewrite_use_compare): Pass data to may_eliminate_iv.
(rewrite_use_outer): Pass data to may_replace_final_value.
(free_loop_data): Clean up the niters cache.
(tree_ssa_iv_optimize_finalize): Free the niters cache.
* tree-ssa-loop-niter.c (find_loop_niter): New function.
(find_loop_niter_by_eval): Use tree_int_cst_lt.
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.50
diff -c -3 -p -r2.50 tree-flow.h
*** tree-flow.h 29 Sep 2004 21:23:35 -0000 2.50
--- tree-flow.h 2 Oct 2004 12:49:45 -0000
*************** void number_of_iterations_cond (tree, tr
*** 658,663 ****
--- 658,664 ----
struct tree_niter_desc *);
bool number_of_iterations_exit (struct loop *, edge,
struct tree_niter_desc *niter);
+ tree find_loop_niter (struct loop *, edge *);
tree loop_niter_by_eval (struct loop *, edge);
tree find_loop_niter_by_eval (struct loop *, edge *);
void estimate_numbers_of_iterations (struct loops *);
Index: tree-ssa-loop-ivcanon.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivcanon.c,v
retrieving revision 2.5
diff -c -3 -p -r2.5 tree-ssa-loop-ivcanon.c
*** tree-ssa-loop-ivcanon.c 1 Oct 2004 18:26:31 -0000 2.5
--- tree-ssa-loop-ivcanon.c 2 Oct 2004 12:49:45 -0000
*************** canonicalize_loop_induction_variables (s
*** 220,231 ****
niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
build_int_cst (TREE_TYPE (niter), 1)));
}
! else if (try_eval)
! niter = find_loop_niter_by_eval (loop, &exit);
!
! if (chrec_contains_undetermined (niter)
! || TREE_CODE (niter) != INTEGER_CST)
! return false;
if (dump_file && (dump_flags & TDF_DETAILS))
{
--- 220,242 ----
niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
build_int_cst (TREE_TYPE (niter), 1)));
}
! else
! {
! /* If the loop has more than one exit, try checking all of them
! for # of iterations determinable through scev. */
! if (!loop->single_exit)
! niter = find_loop_niter (loop, &exit);
!
! /* Finally if everything else fails, try brute force evaluation. */
! if (try_eval
! && (chrec_contains_undetermined (niter)
! || TREE_CODE (niter) != INTEGER_CST))
! niter = find_loop_niter_by_eval (loop, &exit);
!
! if (chrec_contains_undetermined (niter)
! || TREE_CODE (niter) != INTEGER_CST)
! return false;
! }
if (dump_file && (dump_flags & TDF_DETAILS))
{
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.16
diff -c -3 -p -r2.16 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c 1 Oct 2004 09:06:03 -0000 2.16
--- tree-ssa-loop-ivopts.c 2 Oct 2004 12:49:45 -0000
*************** struct version_info
*** 126,134 ****
/* Information attached to loop. */
struct loop_data
{
- struct tree_niter_desc niter;
- /* Number of iterations. */
-
unsigned regs_used; /* Number of registers used. */
};
--- 126,131 ----
*************** struct ivopts_data
*** 201,206 ****
--- 198,206 ----
/* The currently optimized loop. */
struct loop *current_loop;
+ /* Numbers of iterations for all exits of the current loop. */
+ htab_t niters;
+
/* The size of version_info array allocated. */
unsigned version_info_size;
*************** stmt_after_increment (struct loop *loop,
*** 574,579 ****
--- 574,659 ----
}
}
+ /* Element of the table in that we cache the numbers of iterations obtained
+ from exits of the loop. */
+
+ struct nfe_cache_elt
+ {
+ /* The edge for that the number of iterations is cached. */
+ edge exit;
+
+ /* True if the # of iterations was succesfully determined. */
+ bool valid_p;
+
+ /* Description of # of iterations. */
+ struct tree_niter_desc niter;
+ };
+
+ /* Hash function for nfe_cache_elt E. */
+
+ static hashval_t
+ nfe_hash (const void *e)
+ {
+ const struct nfe_cache_elt *elt = e;
+
+ return htab_hash_pointer (elt->exit);
+ }
+
+ /* Equality function for nfe_cache_elt E1 and edge E2. */
+
+ static int
+ nfe_eq (const void *e1, const void *e2)
+ {
+ const struct nfe_cache_elt *elt1 = e1;
+
+ return elt1->exit == e2;
+ }
+
+ /* Returns structure describing number of iterations determined from
+ EXIT of DATA->current_loop, or NULL if something goes wrong. */
+
+ static struct tree_niter_desc *
+ niter_for_exit (struct ivopts_data *data, edge exit)
+ {
+ struct nfe_cache_elt *nfe_desc;
+ PTR *slot;
+
+ slot = htab_find_slot_with_hash (data->niters, exit,
+ htab_hash_pointer (exit),
+ INSERT);
+
+ if (!*slot)
+ {
+ nfe_desc = xmalloc (sizeof (struct nfe_cache_elt));
+ nfe_desc->exit = exit;
+ nfe_desc->valid_p = number_of_iterations_exit (data->current_loop,
+ exit, &nfe_desc->niter);
+ *slot = nfe_desc;
+ }
+ else
+ nfe_desc = *slot;
+
+ if (!nfe_desc->valid_p)
+ return NULL;
+
+ return &nfe_desc->niter;
+ }
+
+ /* Returns structure describing number of iterations determined from
+ single dominating exit of DATA->current_loop, or NULL if something
+ goes wrong. */
+
+ static struct tree_niter_desc *
+ niter_for_single_dom_exit (struct ivopts_data *data)
+ {
+ edge exit = single_dom_exit (data->current_loop);
+
+ if (!exit)
+ return NULL;
+
+ return niter_for_exit (data, exit);
+ }
+
/* Initializes data structures used by the iv optimization pass, stored
in DATA. LOOPS is the loop tree. */
*************** tree_ssa_iv_optimize_init (struct loops
*** 587,592 ****
--- 667,673 ----
sizeof (struct version_info));
data->relevant = BITMAP_XMALLOC ();
data->max_inv_id = 0;
+ data->niters = htab_create (10, nfe_hash, nfe_eq, free);
for (i = 1; i < loops->num; i++)
if (loops->parray[i])
*************** find_givs (struct ivopts_data *data)
*** 940,959 ****
free (body);
}
- /* Determine the number of iterations of the current loop. */
-
- static void
- determine_number_of_iterations (struct ivopts_data *data)
- {
- struct loop *loop = data->current_loop;
- edge exit = single_dom_exit (loop);
-
- if (!exit)
- return;
-
- number_of_iterations_exit (loop, exit, &loop_data (loop)->niter);
- }
-
/* For each ssa name defined in LOOP determines whether it is an induction
variable and if so, its initial value and step. */
--- 1021,1026 ----
*************** static bool
*** 961,967 ****
find_induction_variables (struct ivopts_data *data)
{
unsigned i;
- struct loop *loop = data->current_loop;
bitmap_iterator bi;
if (!find_bivs (data))
--- 1028,1033 ----
*************** find_induction_variables (struct ivopts_
*** 969,993 ****
find_givs (data);
mark_bivs (data);
- determine_number_of_iterations (data);
if (dump_file && (dump_flags & TDF_DETAILS))
{
! if (loop_data (loop)->niter.niter)
{
fprintf (dump_file, " number of iterations ");
! print_generic_expr (dump_file, loop_data (loop)->niter.niter,
! TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, " may be zero if ");
! print_generic_expr (dump_file, loop_data (loop)->niter.may_be_zero,
! TDF_SLIM);
! fprintf (dump_file, "\n");
!
! fprintf (dump_file, " bogus unless ");
! print_generic_expr (dump_file, loop_data (loop)->niter.assumptions,
! TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
};
--- 1035,1055 ----
find_givs (data);
mark_bivs (data);
if (dump_file && (dump_flags & TDF_DETAILS))
{
! struct tree_niter_desc *niter;
!
! niter = niter_for_single_dom_exit (data);
!
! if (niter)
{
fprintf (dump_file, " number of iterations ");
! print_generic_expr (dump_file, niter->niter, TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, " may be zero if ");
! print_generic_expr (dump_file, niter->may_be_zero, TDF_SLIM);
fprintf (dump_file, "\n");
fprintf (dump_file, "\n");
};
*************** static void
*** 1831,1846 ****
add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
{
struct tree_niter_desc *niter;
- struct loop *loop = data->current_loop;
/* We must know where we exit the loop and how many times does it roll. */
! if (!single_dom_exit (loop))
! return;
!
! niter = &loop_data (loop)->niter;
! if (!niter->niter
! || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
! || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
return;
add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
--- 1893,1903 ----
add_iv_outer_candidates (struct ivopts_data *data, struct iv_use *use)
{
struct tree_niter_desc *niter;
/* We must know where we exit the loop and how many times does it roll. */
! niter = niter_for_single_dom_exit (data);
! if (!niter
! || !zero_p (niter->may_be_zero))
return;
add_candidate_1 (data, NULL, NULL, false, IP_NORMAL, use, NULL_TREE);
*************** cand_value_at (struct loop *loop, struct
*** 3005,3018 ****
value compared with to BOUND. */
static bool
! may_eliminate_iv (struct loop *loop,
struct iv_use *use, struct iv_cand *cand,
enum tree_code *compare, tree *bound)
{
basic_block ex_bb;
edge exit;
! struct tree_niter_desc niter, new_niter;
tree wider_type, type, base;
/* For now works only for exits that dominate the loop latch. TODO -- extend
for other conditions inside loop body. */
--- 3062,3076 ----
value compared with to BOUND. */
static bool
! may_eliminate_iv (struct ivopts_data *data,
struct iv_use *use, struct iv_cand *cand,
enum tree_code *compare, tree *bound)
{
basic_block ex_bb;
edge exit;
! struct tree_niter_desc *niter, new_niter;
tree wider_type, type, base;
+ struct loop *loop = data->current_loop;
/* For now works only for exits that dominate the loop latch. TODO -- extend
for other conditions inside loop body. */
*************** may_eliminate_iv (struct loop *loop,
*** 3029,3039 ****
if (flow_bb_inside_loop_p (loop, exit->dest))
return false;
! niter.niter = NULL_TREE;
! number_of_iterations_exit (loop, exit, &niter);
! if (!niter.niter
! || !integer_nonzerop (niter.assumptions)
! || !integer_zerop (niter.may_be_zero))
return false;
if (exit->flags & EDGE_TRUE_VALUE)
--- 3087,3095 ----
if (flow_bb_inside_loop_p (loop, exit->dest))
return false;
! niter = niter_for_exit (data, exit);
! if (!niter
! || !zero_p (niter->may_be_zero))
return false;
if (exit->flags & EDGE_TRUE_VALUE)
*************** may_eliminate_iv (struct loop *loop,
*** 3041,3047 ****
else
*compare = NE_EXPR;
! *bound = cand_value_at (loop, cand, use->stmt, niter.niter);
/* Let us check there is not some problem with overflows, by checking that
the number of iterations is unchanged. */
--- 3097,3103 ----
else
*compare = NE_EXPR;
! *bound = cand_value_at (loop, cand, use->stmt, niter->niter);
/* Let us check there is not some problem with overflows, by checking that
the number of iterations is unchanged. */
*************** may_eliminate_iv (struct loop *loop,
*** 3060,3068 ****
return false;
wider_type = TREE_TYPE (new_niter.niter);
! if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter.niter)))
! wider_type = TREE_TYPE (niter.niter);
! if (!operand_equal_p (fold_convert (wider_type, niter.niter),
fold_convert (wider_type, new_niter.niter), 0))
return false;
--- 3116,3124 ----
return false;
wider_type = TREE_TYPE (new_niter.niter);
! if (TYPE_PRECISION (wider_type) < TYPE_PRECISION (TREE_TYPE (niter->niter)))
! wider_type = TREE_TYPE (niter->niter);
! if (!operand_equal_p (fold_convert (wider_type, niter->niter),
fold_convert (wider_type, new_niter.niter), 0))
return false;
*************** determine_use_iv_cost_condition (struct
*** 3085,3091 ****
return;
}
! if (may_eliminate_iv (data->current_loop, use, cand, &compare, &bound))
{
bitmap depends_on = NULL;
unsigned cost = force_var_cost (data, bound, &depends_on);
--- 3141,3147 ----
return;
}
! if (may_eliminate_iv (data, use, cand, &compare, &bound))
{
bitmap depends_on = NULL;
unsigned cost = force_var_cost (data, bound, &depends_on);
*************** determine_use_iv_cost_condition (struct
*** 3112,3119 ****
a direct computation. If so, the formula is stored to *VALUE. */
static bool
! may_replace_final_value (struct loop *loop, struct iv_use *use, tree *value)
{
edge exit;
struct tree_niter_desc *niter;
--- 3168,3177 ----
a direct computation. If so, the formula is stored to *VALUE. */
static bool
! may_replace_final_value (struct ivopts_data *data, struct iv_use *use,
! tree *value)
{
+ struct loop *loop = data->current_loop;
edge exit;
struct tree_niter_desc *niter;
*************** may_replace_final_value (struct loop *lo
*** 3124,3133 ****
gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
bb_for_stmt (use->stmt)));
! niter = &loop_data (loop)->niter;
! if (!niter->niter
! || !operand_equal_p (niter->assumptions, boolean_true_node, 0)
! || !operand_equal_p (niter->may_be_zero, boolean_false_node, 0))
return false;
*value = iv_value (use->iv, niter->niter);
--- 3182,3190 ----
gcc_assert (dominated_by_p (CDI_DOMINATORS, exit->src,
bb_for_stmt (use->stmt)));
! niter = niter_for_single_dom_exit (data);
! if (!niter
! || !zero_p (niter->may_be_zero))
return false;
*value = iv_value (use->iv, niter->niter);
*************** determine_use_iv_cost_outer (struct ivop
*** 3149,3155 ****
if (!cand->iv)
{
! if (!may_replace_final_value (loop, use, &value))
{
set_use_iv_cost (data, use, cand, INFTY, NULL);
return;
--- 3206,3212 ----
if (!cand->iv)
{
! if (!may_replace_final_value (data, use, &value))
{
set_use_iv_cost (data, use, cand, INFTY, NULL);
return;
*************** rewrite_use_compare (struct ivopts_data
*** 4062,4069 ****
block_stmt_iterator bsi = stmt_for_bsi (use->stmt);
enum tree_code compare;
! if (may_eliminate_iv (data->current_loop,
! use, cand, &compare, &bound))
{
op = force_gimple_operand (unshare_expr (bound), &stmts,
true, NULL_TREE);
--- 4119,4125 ----
block_stmt_iterator bsi = stmt_for_bsi (use->stmt);
enum tree_code compare;
! if (may_eliminate_iv (data, use, cand, &compare, &bound))
{
op = force_gimple_operand (unshare_expr (bound), &stmts,
true, NULL_TREE);
*************** rewrite_use_outer (struct ivopts_data *d
*** 4237,4243 ****
{
if (!cand->iv)
{
! bool ok = may_replace_final_value (data->current_loop, use, &value);
gcc_assert (ok);
}
else
--- 4293,4299 ----
{
if (!cand->iv)
{
! bool ok = may_replace_final_value (data, use, &value);
gcc_assert (ok);
}
else
*************** free_loop_data (struct ivopts_data *data
*** 4358,4363 ****
--- 4414,4421 ----
unsigned i, j;
bitmap_iterator bi;
+ htab_empty (data->niters);
+
EXECUTE_IF_SET_IN_BITMAP (data->relevant, 0, i, bi)
{
struct version_info *info;
*************** tree_ssa_iv_optimize_finalize (struct lo
*** 4433,4438 ****
--- 4491,4497 ----
free_loop_data (data);
free (data->version_info);
BITMAP_XFREE (data->relevant);
+ htab_delete (data->niters);
VARRAY_FREE (decl_rtl_to_reset);
VARRAY_FREE (data->iv_uses);
Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.10
diff -c -3 -p -r2.10 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c 1 Oct 2004 09:06:06 -0000 2.10
--- tree-ssa-loop-niter.c 2 Oct 2004 12:49:45 -0000
*************** number_of_iterations_exit (struct loop *
*** 688,693 ****
--- 688,762 ----
return integer_onep (niter->assumptions);
}
+ /* Try to determine the number of iterations of LOOP. If we succeed,
+ expression giving number of iterations is returned and *EXIT is
+ set to the edge from that the information is obtained. Otherwise
+ chrec_dont_know is returned. */
+
+ tree
+ find_loop_niter (struct loop *loop, edge *exit)
+ {
+ unsigned n_exits, i;
+ edge *exits = get_loop_exit_edges (loop, &n_exits);
+ edge ex;
+ tree niter = NULL_TREE, aniter;
+ struct tree_niter_desc desc;
+
+ *exit = NULL;
+ for (i = 0; i < n_exits; i++)
+ {
+ ex = exits[i];
+ if (!just_once_each_iteration_p (loop, ex->src))
+ continue;
+
+ if (!number_of_iterations_exit (loop, ex, &desc))
+ continue;
+
+ if (nonzero_p (desc.may_be_zero))
+ {
+ /* We exit in the first iteration through this exit.
+ We won't find anything better. */
+ niter = build_int_cst_type (unsigned_type_node, 0);
+ *exit = ex;
+ break;
+ }
+
+ if (!zero_p (desc.may_be_zero))
+ continue;
+
+ aniter = desc.niter;
+
+ if (!niter)
+ {
+ /* Nothing recorded yet. */
+ niter = aniter;
+ *exit = ex;
+ continue;
+ }
+
+ /* Prefer constants, the lower the better. */
+ if (TREE_CODE (aniter) != INTEGER_CST)
+ continue;
+
+ if (TREE_CODE (niter) != INTEGER_CST)
+ {
+ niter = aniter;
+ *exit = ex;
+ continue;
+ }
+
+ if (tree_int_cst_lt (aniter, niter))
+ {
+ niter = aniter;
+ *exit = ex;
+ continue;
+ }
+ }
+ free (exits);
+
+ return niter ? niter : chrec_dont_know;
+ }
+
/*
Analysis of a number of iterations of a loop by a brute-force evaluation.
*************** find_loop_niter_by_eval (struct loop *lo
*** 920,932 ****
continue;
aniter = loop_niter_by_eval (loop, ex);
! if (chrec_contains_undetermined (aniter)
! || TREE_CODE (aniter) != INTEGER_CST)
continue;
if (niter
! && !nonzero_p (fold (build2 (LT_EXPR, boolean_type_node,
! aniter, niter))))
continue;
niter = aniter;
--- 989,999 ----
continue;
aniter = loop_niter_by_eval (loop, ex);
! if (chrec_contains_undetermined (aniter))
continue;
if (niter
! && !tree_int_cst_lt (aniter, niter))
continue;
niter = aniter;