Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi Zdenek,
On 05/31/2011 10:04 AM, Zdenek Dvorak wrote:
Hi,
As far as I can tell, what is current calculated in i_bound (and assigned to
nb_iterations_upper_bound), is the maximum amount of times any statement in
the
loop is executed, where any includes exit tests. Differently put, the maximum
amount of times the loop header is executed.
hmm... this is rather confusing, I don't really recall why I gave
nb_iterations_upper_bound a different semantics from any other instance
of what # of iterations of a loop means.
This is confirmed by this comment in tree-vrp.c:
/* Try to use estimated number of iterations for the loop to constrain the
final value in the evolution.
We are interested in the number of executions of the latch, while
nb_iterations_upper_bound includes the last execution of the exit test.
*/
I modified the patch to improved the comment.
I think a better fix would be to make the nb_iterations_upper_bound semantics
consistent with that of nb_iterations. Let me try to do it, hopefully this
should
be mostly mechanical,
This patch changes the semantics of nb_iterations_upper_bound and
nb_iterations_estimate, to mean: the amount of latch executions.
That change is countered at all use sites, except for
tree-ssa-loop-ivopts.c:may_eliminate_iv.
Passed x86_64 bootstrapping and reg-testing.
OK for trunk?
2011-06-10 Zdenek Dvorak o...@ucw.cz
Tom de Vries t...@codesourcery.com
PR target/45098
* cfgloop.h (nb_iterations_upper_bound, nb_iterations_estimate):
Document changed semantics.
(max_stmt_executions, max_stmt_executions_int): Declare.
* tree-data-ref.c (estimated_loop_iterations)
(estimated_loop_iterations_int): Move functions...
* tree-ssa-loop-niter.c (estimated_loop_iterations)
(estimated_loop_iterations_int): here.
(record_estimate): Change nb_iterations_upper_bound and
nb_iterations_estimate semantics.
(max_stmt_executions, max_stmt_executions_int): New function.
* tree-data-ref.c (estimated_loop_iterations_tree): Rename to ...
(max_stmt_executions_tree): this.
(analyze_miv_subscript): Use max_stmt_executions_tree instead of
estimated_loop_iterations_tree.
tree-ssa-loop-ivopts.c (avg_loop_niter): Use
max_stmt_executions_int instead of estimated_loop_iterations_int.
* predict.c (predict_loops): Idem.
* tree-parloops.c (parallelize_loops): Idem.
* tree-data-ref.c (analyze_siv_subscript_cst_affine)
(compute_overlap_steps_for_affine_1_2, analyze_subscript_affine_affine)
(init_omega_for_ddr_1): Idem.
* tree-ssa-loop-prefetch.c (determine_loop_nest_reuse)
(loop_prefetch_arrays): Idem
* graphite-sese-to-poly.c (build_loop_iteration_domains): Use
max_stmt_executions instead of estimated_loop_iterations.
* tree-data-ref.c (estimated_loop_iterations_tree): Idem.
* tree-vrp.c (adjust_range_with_scev): Use estimated_loop_iterations
instead of nb_iterations_upper_bound.
Index: gcc/tree-vrp.c
===
--- gcc/tree-vrp.c (revision 174810)
+++ gcc/tree-vrp.c (working copy)
@@ -3403,44 +3403,42 @@ adjust_range_with_scev (value_range_t *v
tmax = TYPE_MAX_VALUE (type);
/* Try to use estimated number of iterations for the loop to constrain the
- final value in the evolution.
- We are interested in the number of executions of the latch, while
- nb_iterations_upper_bound includes the last execution of the exit test. */
+ final value in the evolution. */
if (TREE_CODE (step) == INTEGER_CST
- loop-any_upper_bound
- !double_int_zero_p (loop-nb_iterations_upper_bound)
is_gimple_val (init)
(TREE_CODE (init) != SSA_NAME
|| get_value_range (init)-type == VR_RANGE))
{
- value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- double_int dtmp;
- bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step));
- int overflow = 0;
+ double_int nit;
- dtmp = double_int_mul_with_sign (tree_to_double_int (step),
- double_int_sub (
- loop-nb_iterations_upper_bound,
- double_int_one),
- unsigned_p, overflow);
- /* If the multiplication overflowed we can't do a meaningful
- adjustment. Likewise if the result doesn't fit in the type
- of the induction variable. For a signed type we have to
- check whether the result has the expected signedness which
- is that of the step as nb_iterations_upper_bound is unsigned. */
- if (!overflow
- double_int_fits_to_tree_p (TREE_TYPE (init), dtmp)
- (unsigned_p
- || ((dtmp.high ^ TREE_INT_CST_HIGH (step)) = 0)))
+ if (estimated_loop_iterations (loop,
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
On 05/30/2011 02:38 PM, Zdenek Dvorak wrote:
Hi,
The header block of the loop is bb 4, the latch block is bb 3:
...
(gdb) p loop.header.index
$4 = 4
(gdb) p loop.latch.index
$5 = 3
...
The number of times the latch edge is executed, is 10.
But loop-nb_iterations_upper_bound, or max_niter is 11:
this is a bit strange, it looks like the # of iterations estimation is setting
nb_iterations_upper_bound too conservatively (or I gave
nb_iterations_upper_bound
a different semantics than I remember -- but both my memory and the comment
in cfgloop.h
suggest that nb_iterations_upper_bound = nb_iterations, i.e., that it should
be 10 in your
example),
The actual values of nb_iterations_upper_bound are determined by this code
fragment in record_estimate.
/* Records that AT_STMT is executed at most BOUND + 1 times in LOOP. 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 BOUND is expected to be close to the real number
of iterations. UPPER is true if we are sure the loop iterates at most
BOUND times. I_BOUND is an unsigned double_int upper estimate on BOUND. */
static void
record_estimate (struct loop *loop, tree bound, double_int i_bound,
gimple at_stmt, bool is_exit, bool realistic, bool upper)
{
...
/* Update the number of iteration estimates according to the bound.
If at_stmt is an exit, then every statement in the loop is
executed at most BOUND + 1 times. If it is not an exit, then
some of the statements before it could be executed BOUND + 2
times, if an exit of LOOP is before stmt. */
exit = single_exit (loop);
if (is_exit
|| (exit != NULL
dominated_by_p (CDI_DOMINATORS,
exit-src, gimple_bb (at_stmt
delta = double_int_one;
else
delta = double_int_two;
i_bound = double_int_add (i_bound, delta);
As far as I can tell, what is current calculated in i_bound (and assigned to
nb_iterations_upper_bound), is the maximum amount of times any statement in the
loop is executed, where any includes exit tests. Differently put, the maximum
amount of times the loop header is executed.
This is confirmed by this comment in tree-vrp.c:
/* Try to use estimated number of iterations for the loop to constrain the
final value in the evolution.
We are interested in the number of executions of the latch, while
nb_iterations_upper_bound includes the last execution of the exit test. */
I modified the patch to improved the comment.
Ok for trunk?
Thanks,
- Tom
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 173734)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -4391,8 +4391,14 @@ may_eliminate_iv (struct ivopts_data *da
{
if (!estimated_loop_iterations (loop, true, max_niter))
return false;
- /* The loop bound is already adjusted by adding 1. */
- if (double_int_ucmp (max_niter, period_value) 0)
+ /* (a) loop-nb_iterations_upper_bound (assigned to max_niter)
+ includes the last execution of the exit test.
+ (b) The number of distinct values of the cand is
+ period_value + 1.
+ So, the transformation is allowed if
+ max_niter = period_value + 1. */
+ period_value = double_int_add (period_value, double_int_one);
+ if (double_int_ucmp (max_niter, period_value) 0)
return false;
}
else
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi, As far as I can tell, what is current calculated in i_bound (and assigned to nb_iterations_upper_bound), is the maximum amount of times any statement in the loop is executed, where any includes exit tests. Differently put, the maximum amount of times the loop header is executed. hmm... this is rather confusing, I don't really recall why I gave nb_iterations_upper_bound a different semantics from any other instance of what # of iterations of a loop means. This is confirmed by this comment in tree-vrp.c: /* Try to use estimated number of iterations for the loop to constrain the final value in the evolution. We are interested in the number of executions of the latch, while nb_iterations_upper_bound includes the last execution of the exit test. */ I modified the patch to improved the comment. I think a better fix would be to make the nb_iterations_upper_bound semantics consistent with that of nb_iterations. Let me try to do it, hopefully this should be mostly mechanical, Zdenek
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi, The header block of the loop is bb 4, the latch block is bb 3: ... (gdb) p loop.header.index $4 = 4 (gdb) p loop.latch.index $5 = 3 ... The number of times the latch edge is executed, is 10. But loop-nb_iterations_upper_bound, or max_niter is 11: this is a bit strange, it looks like the # of iterations estimation is setting nb_iterations_upper_bound too conservatively (or I gave nb_iterations_upper_bound a different semantics than I remember -- but both my memory and the comment in cfgloop.h suggest that nb_iterations_upper_bound = nb_iterations, i.e., that it should be 10 in your example), Zdenek
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi Zdenek,
On 05/21/2011 07:59 PM, Tom de Vries wrote:
On 05/21/2011 02:24 PM, Zdenek Dvorak wrote:
* tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix
estimated_loop_iterations comparison.
I don't think this part is correct, though:
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 173734)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -4391,8 +4391,13 @@ may_eliminate_iv (struct ivopts_data *da
{
if (!estimated_loop_iterations (loop, true, max_niter))
return false;
- /* The loop bound is already adjusted by adding 1. */
- if (double_int_ucmp (max_niter, period_value) 0)
+ /* The max iterations applies also to the number of times
the loop
+ exit condition is executed. The number of distinct
values of
+ the cand is period_value + 1. So, test for
+ 'period_value + 1 = max_iterations'.
+ */
+ period_value = double_int_add (period_value, double_int_one);
+ if (double_int_ucmp (max_niter, period_value) 0)
return false;
}
else
max_niter is the upper bound on the number of iterations of the loop, i.e.,
the number
of executions of its latch edge.
max_niter is set from estimated_loop_iterations, meaning from
loop-nb_iterations_upper_bound.
consider:
...
void f(int *a)
{
int i;
for (i = 0; i 10; ++i)
a[i] = 0;
}
...
at ivopts, it looks like this (compiled with -Os -fno-tree-vrp
-fno-tree-dominator-opts -fno-tree-loop-ivcanon, to get a source-like
representation)
...
f (int * a)
{
int i;
int * D.2009;
unsigned int D.2008;
unsigned int i.0;
bb 2:
goto bb 4;
bb 3:
i.0_3 = (unsigned int) i_1;
D.2008_4 = i.0_3 * 4;
D.2009_6 = a_5(D) + D.2008_4;
*D.2009_6 = 0;
i_7 = i_1 + 1;
bb 4:
# i_1 = PHI 0(2), i_7(3)
if (i_1 = 9)
goto bb 3;
else
goto bb 5;
bb 5:
return;
}
...
The header block of the loop is bb 4, the latch block is bb 3:
...
(gdb) p loop.header.index
$4 = 4
(gdb) p loop.latch.index
$5 = 3
...
The number of times the latch edge is executed, is 10.
But loop-nb_iterations_upper_bound, or max_niter is 11:
...
(gdb) p *loop
$1 = {num = 1, ninsns = 0, header = 0xf7dc2440, latch = 0xf7dc2400,
lpt_decision
= {decision = LPT_NONE, times = 0}, av_ninsns = 0, num_nodes = 2, superloops =
0xf7db6ee8, inner = 0x0, next = 0x0,
aux = 0x0, nb_iterations = 0xf7d3d540, nb_iterations_upper_bound = {low =
11,
high = 0}, nb_iterations_estimate = {low = 11, high = 0}, any_upper_bound = 1
'\001', any_estimate = 1 '\001',
can_be_parallel = 0 '\000', estimate_state = EST_AVAILABLE, bounds =
0xf7d3da2c, exits = 0xf7dc3d70}
...
Therefore, the control induction variable of the loop
will (at the exit statement) achieve at most max_niter + 1 different values.
Based on what I observe, I'd say the control induction variable of the loop
will
achieve at most max_niter different values.
Any thoughts on my observations above?
Thanks,
- Tom
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
Hi,
Would it be possible to add the handling of these cases
to estimate_numbers_of_iterations, rather than doing it just for ivopts?
Yes, I did that now.
Thanks,
- Tom
2011-05-05 Tom de Vries t...@codesourcery.com
PR target/45098
* tree-ssa-loop-niter.c (infer_loop_bounds_from_pointer_arith): New
function.
(infer_loop_bounds_from_undefined): Use new function.
this is OK.
* tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix
estimated_loop_iterations comparison.
I don't think this part is correct, though:
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 173734)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -4391,8 +4391,13 @@ may_eliminate_iv (struct ivopts_data *da
{
if (!estimated_loop_iterations (loop, true, max_niter))
return false;
- /* The loop bound is already adjusted by adding 1. */
- if (double_int_ucmp (max_niter, period_value) 0)
+ /* The max iterations applies also to the number of times the
loop
+ exit condition is executed. The number of distinct values
of
+ the cand is period_value + 1. So, test for
+ 'period_value + 1 = max_iterations'.
+ */
+ period_value = double_int_add (period_value, double_int_one);
+ if (double_int_ucmp (max_niter, period_value) 0)
return false;
}
else
max_niter is the upper bound on the number of iterations of the loop, i.e., the
number
of executions of its latch edge. Therefore, the control induction variable of
the loop
will (at the exit statement) achieve at most max_niter + 1 different values.
Conversely,
the number of distinct values that the control iv can represent is period + 1
(naming of
the period variable is a bit missleading). Thus, the correct test is
# of available values = # of required values, equivalently
period + 1 = max_niter + 1, equivalently
period = max_niter, i.e.,
the current test.
Zdenek
Re: [PATCH PR45098, 7/10] Nowrap limits iterations
On 05/21/2011 02:24 PM, Zdenek Dvorak wrote:
* tree-ssa-loop-ivopts.c (may_eliminate_iv): Fix
estimated_loop_iterations comparison.
I don't think this part is correct, though:
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 173734)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -4391,8 +4391,13 @@ may_eliminate_iv (struct ivopts_data *da
{
if (!estimated_loop_iterations (loop, true, max_niter))
return false;
- /* The loop bound is already adjusted by adding 1. */
- if (double_int_ucmp (max_niter, period_value) 0)
+ /* The max iterations applies also to the number of times the
loop
+ exit condition is executed. The number of distinct values
of
+ the cand is period_value + 1. So, test for
+ 'period_value + 1 = max_iterations'.
+ */
+ period_value = double_int_add (period_value, double_int_one);
+ if (double_int_ucmp (max_niter, period_value) 0)
return false;
}
else
max_niter is the upper bound on the number of iterations of the loop, i.e.,
the number
of executions of its latch edge.
max_niter is set from estimated_loop_iterations, meaning from
loop-nb_iterations_upper_bound.
consider:
...
void f(int *a)
{
int i;
for (i = 0; i 10; ++i)
a[i] = 0;
}
...
at ivopts, it looks like this (compiled with -Os -fno-tree-vrp
-fno-tree-dominator-opts -fno-tree-loop-ivcanon, to get a source-like
representation)
...
f (int * a)
{
int i;
int * D.2009;
unsigned int D.2008;
unsigned int i.0;
bb 2:
goto bb 4;
bb 3:
i.0_3 = (unsigned int) i_1;
D.2008_4 = i.0_3 * 4;
D.2009_6 = a_5(D) + D.2008_4;
*D.2009_6 = 0;
i_7 = i_1 + 1;
bb 4:
# i_1 = PHI 0(2), i_7(3)
if (i_1 = 9)
goto bb 3;
else
goto bb 5;
bb 5:
return;
}
...
The header block of the loop is bb 4, the latch block is bb 3:
...
(gdb) p loop.header.index
$4 = 4
(gdb) p loop.latch.index
$5 = 3
...
The number of times the latch edge is executed, is 10.
But loop-nb_iterations_upper_bound, or max_niter is 11:
...
(gdb) p *loop
$1 = {num = 1, ninsns = 0, header = 0xf7dc2440, latch = 0xf7dc2400, lpt_decision
= {decision = LPT_NONE, times = 0}, av_ninsns = 0, num_nodes = 2, superloops =
0xf7db6ee8, inner = 0x0, next = 0x0,
aux = 0x0, nb_iterations = 0xf7d3d540, nb_iterations_upper_bound = {low = 11,
high = 0}, nb_iterations_estimate = {low = 11, high = 0}, any_upper_bound = 1
'\001', any_estimate = 1 '\001',
can_be_parallel = 0 '\000', estimate_state = EST_AVAILABLE, bounds =
0xf7d3da2c, exits = 0xf7dc3d70}
...
Therefore, the control induction variable of the loop
will (at the exit statement) achieve at most max_niter + 1 different values.
Based on what I observe, I'd say the control induction variable of the loop will
achieve at most max_niter different values.
Conversely,
the number of distinct values that the control iv can represent is period + 1
(naming of
the period variable is a bit missleading).
agree.
Thanks,
- Tom
[PATCH PR45098, 7/10] Nowrap limits iterations
On 05/17/2011 09:20 AM, Tom de Vries wrote:
On 05/17/2011 09:10 AM, Tom de Vries wrote:
Hi Zdenek,
I have a patch set for for PR45098.
01_object-size-target.patch
02_pr45098-rtx-cost-set.patch
03_pr45098-computation-cost.patch
04_pr45098-iv-init-cost.patch
05_pr45098-bound-cost.patch
06_pr45098-bound-cost.test.patch
07_pr45098-nowrap-limits-iterations.patch
08_pr45098-nowrap-limits-iterations.test.patch
09_pr45098-shift-add-cost.patch
10_pr45098-shift-add-cost.test.patch
I will sent out the patches individually.
OK for trunk?
Thanks,
- Tom
Resubmitting with comment.
This patch attemps to estimate the number of iterations of the loop based on
nonwrapping arithmetic in the loop body.
2011-05-05 Tom de Vries t...@codesourcery.com
PR target/45098
* tree-ssa-loop-ivopts.c (struct ivopts_data): Add fields
max_iterations_p and max_iterations.
(is_nonwrap_use, max_loop_iterations, set_max_iterations): New function.
(may_eliminate_iv): Use max_iterations_p and max_iterations.
(tree_ssa_iv_optimize_loop): Use set_max_iterations.
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 173355)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -291,6 +291,12 @@ struct ivopts_data
/* Whether the loop body includes any function calls. */
bool body_includes_call;
+
+ /* Whether max_iterations is valid. */
+ bool max_iterations_p;
+
+ /* Maximum number of iterations of current_loop. */
+ double_int max_iterations;
};
/* An assignment of iv candidates to uses. */
@@ -4319,6 +4325,108 @@ iv_elimination_compare (struct ivopts_da
return (exit-flags EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
+/* Determine if USE contains non-wrapping arithmetic. */
+
+static bool
+is_nonwrap_use (struct ivopts_data *data, struct iv_use *use)
+{
+ gimple stmt = use-stmt;
+ tree var, ptr, ptr_type;
+
+ if (!is_gimple_assign (stmt))
+return false;
+
+ switch (gimple_assign_rhs_code (stmt))
+{
+case POINTER_PLUS_EXPR:
+ ptr = gimple_assign_rhs1 (stmt);
+ ptr_type = TREE_TYPE (ptr);
+ var = gimple_assign_rhs2 (stmt);
+ if (!expr_invariant_in_loop_p (data-current_loop, ptr))
+return false;
+ break;
+case ARRAY_REF:
+ ptr = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 0);
+ ptr_type = build_pointer_type (TREE_TYPE (gimple_assign_rhs1 (stmt)));
+ var = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 1);
+ break;
+default:
+ return false;
+}
+
+ if (!nowrap_type_p (ptr_type))
+return false;
+
+ if (TYPE_PRECISION (ptr_type) != TYPE_PRECISION (TREE_TYPE (var)))
+return false;
+
+ return true;
+}
+
+/* Attempt to infer maximum number of loop iterations of DATA-current_loop
+ from uses in loop containing non-wrapping arithmetic. If successful,
+ return true, and return maximum iterations in MAX_NITER. */
+
+static bool
+max_loop_iterations (struct ivopts_data *data, double_int *max_niter)
+{
+ struct iv_use *use;
+ struct iv *iv;
+ bool found = false;
+ double_int period;
+ gimple stmt;
+ unsigned i;
+
+ for (i = 0; i n_iv_uses (data); i++)
+{
+ use = iv_use (data, i);
+
+ stmt = use-stmt;
+ if (!just_once_each_iteration_p (data-current_loop, gimple_bb (stmt)))
+ continue;
+
+ if (!is_nonwrap_use (data, use))
+continue;
+
+ iv = use-iv;
+ if (iv-step == NULL_TREE || TREE_CODE (iv-step) != INTEGER_CST)
+ continue;
+ period = tree_to_double_int (iv_period (iv));
+
+ if (found)
+*max_niter = double_int_umin (*max_niter, period);
+ else
+{
+ found = true;
+ *max_niter = period;
+}
+}
+
+ return found;
+}
+
+/* Initializes DATA-max_iterations and DATA-max_iterations_p. */
+
+static void
+set_max_iterations (struct ivopts_data *data)
+{
+ double_int max_niter, max_niter2;
+ bool estimate1, estimate2;
+
+ data-max_iterations_p = false;
+ estimate1 = estimated_loop_iterations (data-current_loop, true, max_niter);
+ estimate2 = max_loop_iterations (data, max_niter2);
+ if (!(estimate1 || estimate2))
+return;
+ if (estimate1 estimate2)
+data-max_iterations = double_int_umin (max_niter, max_niter2);
+ else if (estimate1)
+data-max_iterations = max_niter;
+ else
+data-max_iterations = max_niter2;
+ data-max_iterations_p = true;
+}
+
/* Check whether it is possible to express the condition in USE by comparison
of candidate CAND. If so, store the value compared with to BOUND. */
@@ -4391,10 +4499,10 @@ may_eliminate_iv (struct ivopts_data *da
/* See if we can take advantage of infered loop bound information. */
if (loop_only_exit_p (loop, exit))
{
- if (!estimated_loop_iterations (loop, true, max_niter))
+ if (!data-max_iterations_p)
return false;
/*
[PATCH, PR45098, 7/10]
On 05/17/2011 09:10 AM, Tom de Vries wrote:
Hi Zdenek,
I have a patch set for for PR45098.
01_object-size-target.patch
02_pr45098-rtx-cost-set.patch
03_pr45098-computation-cost.patch
04_pr45098-iv-init-cost.patch
05_pr45098-bound-cost.patch
06_pr45098-bound-cost.test.patch
07_pr45098-nowrap-limits-iterations.patch
08_pr45098-nowrap-limits-iterations.test.patch
09_pr45098-shift-add-cost.patch
10_pr45098-shift-add-cost.test.patch
I will sent out the patches individually.
OK for trunk?
Thanks,
- Tom
2011-05-05 Tom de Vries t...@codesourcery.com
PR target/45098
* tree-ssa-loop-ivopts.c (struct ivopts_data): Add fields
max_iterations_p and max_iterations.
(is_nonwrap_use, max_loop_iterations, set_max_iterations): New function.
(may_eliminate_iv): Use max_iterations_p and max_iterations.
(tree_ssa_iv_optimize_loop): Use set_max_iterations.
Index: gcc/tree-ssa-loop-ivopts.c
===
--- gcc/tree-ssa-loop-ivopts.c (revision 173355)
+++ gcc/tree-ssa-loop-ivopts.c (working copy)
@@ -291,6 +291,12 @@ struct ivopts_data
/* Whether the loop body includes any function calls. */
bool body_includes_call;
+
+ /* Whether max_iterations is valid. */
+ bool max_iterations_p;
+
+ /* Maximum number of iterations of current_loop. */
+ double_int max_iterations;
};
/* An assignment of iv candidates to uses. */
@@ -4319,6 +4325,108 @@ iv_elimination_compare (struct ivopts_da
return (exit-flags EDGE_TRUE_VALUE ? EQ_EXPR : NE_EXPR);
}
+/* Determine if USE contains non-wrapping arithmetic. */
+
+static bool
+is_nonwrap_use (struct ivopts_data *data, struct iv_use *use)
+{
+ gimple stmt = use-stmt;
+ tree var, ptr, ptr_type;
+
+ if (!is_gimple_assign (stmt))
+return false;
+
+ switch (gimple_assign_rhs_code (stmt))
+{
+case POINTER_PLUS_EXPR:
+ ptr = gimple_assign_rhs1 (stmt);
+ ptr_type = TREE_TYPE (ptr);
+ var = gimple_assign_rhs2 (stmt);
+ if (!expr_invariant_in_loop_p (data-current_loop, ptr))
+return false;
+ break;
+case ARRAY_REF:
+ ptr = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 0);
+ ptr_type = build_pointer_type (TREE_TYPE (gimple_assign_rhs1 (stmt)));
+ var = TREE_OPERAND ((gimple_assign_rhs1 (stmt)), 1);
+ break;
+default:
+ return false;
+}
+
+ if (!nowrap_type_p (ptr_type))
+return false;
+
+ if (TYPE_PRECISION (ptr_type) != TYPE_PRECISION (TREE_TYPE (var)))
+return false;
+
+ return true;
+}
+
+/* Attempt to infer maximum number of loop iterations of DATA-current_loop
+ from uses in loop containing non-wrapping arithmetic. If successful,
+ return true, and return maximum iterations in MAX_NITER. */
+
+static bool
+max_loop_iterations (struct ivopts_data *data, double_int *max_niter)
+{
+ struct iv_use *use;
+ struct iv *iv;
+ bool found = false;
+ double_int period;
+ gimple stmt;
+ unsigned i;
+
+ for (i = 0; i n_iv_uses (data); i++)
+{
+ use = iv_use (data, i);
+
+ stmt = use-stmt;
+ if (!just_once_each_iteration_p (data-current_loop, gimple_bb (stmt)))
+ continue;
+
+ if (!is_nonwrap_use (data, use))
+continue;
+
+ iv = use-iv;
+ if (iv-step == NULL_TREE || TREE_CODE (iv-step) != INTEGER_CST)
+ continue;
+ period = tree_to_double_int (iv_period (iv));
+
+ if (found)
+*max_niter = double_int_umin (*max_niter, period);
+ else
+{
+ found = true;
+ *max_niter = period;
+}
+}
+
+ return found;
+}
+
+/* Initializes DATA-max_iterations and DATA-max_iterations_p. */
+
+static void
+set_max_iterations (struct ivopts_data *data)
+{
+ double_int max_niter, max_niter2;
+ bool estimate1, estimate2;
+
+ data-max_iterations_p = false;
+ estimate1 = estimated_loop_iterations (data-current_loop, true, max_niter);
+ estimate2 = max_loop_iterations (data, max_niter2);
+ if (!(estimate1 || estimate2))
+return;
+ if (estimate1 estimate2)
+data-max_iterations = double_int_umin (max_niter, max_niter2);
+ else if (estimate1)
+data-max_iterations = max_niter;
+ else
+data-max_iterations = max_niter2;
+ data-max_iterations_p = true;
+}
+
/* Check whether it is possible to express the condition in USE by comparison
of candidate CAND. If so, store the value compared with to BOUND. */
@@ -4391,10 +4499,10 @@ may_eliminate_iv (struct ivopts_data *da
/* See if we can take advantage of infered loop bound information. */
if (loop_only_exit_p (loop, exit))
{
- if (!estimated_loop_iterations (loop, true, max_niter))
+ if (!data-max_iterations_p)
return false;
/* The loop bound is already adjusted by adding 1. */
- if (double_int_ucmp (max_niter, period_value) 0)
+ if (double_int_ucmp (data-max_iterations, period_value) 0)
return false;
