On Wed, Oct 8, 2014 at 5:35 AM, Bin Cheng <bin.ch...@arm.com> wrote:
> Hi,
> This patch is posted long before in a series of patches at
> https://gcc.gnu.org/ml/gcc-patches/2014-07/msg01392.html . Since the
> preceding patch is changed according to review comments, also because it's
> long time not reviewed, I rebased and updated this patch as attached.
>
> With this patch, spec2k/fp can be improved a little on aarch64.
> Bootstrap and test on x86_64 and x86, I am also prepared to fix any
> regression in the future. Is it OK?
+ wide_int max_wi = wi::max_value (TYPE_PRECISION (type), UNSIGNED);
+ max_val = wi::to_widest (wide_int_to_tree (type, max_wi));
ick - there must be a better way to "extend" max_wi to "infinite"
precision. Mike?
/* We need to know that the candidate induction variable does not overflow.
- While more complex analysis may be used to prove this, for now just
- check that the variable appears in the original program and that it
- is computed in a type that guarantees no overflows. */
+ Apart from checking that the variable appears in the original program
+ and that is is computed in a type that guarantees no overflows, we also
+ check no wrapping periord of the variable covers the niter if it has
+ unsigned type. More complex analysis may be used to prove this. */
cand_type = TREE_TYPE (cand->iv->base);
- if (cand->pos != IP_ORIGINAL || !nowrap_type_p (cand_type))
+ if ((cand->pos != IP_ORIGINAL || !nowrap_type_p (cand_type))
+ && !nowrap_cand_for_loop_niter_p (data, use, cand, niter))
return false;
After reading this (and the two functions related) I still don't get
what you are after ;) What is "no wrapping period of the variable
covers the niter"? Somehow if nowrap_cand_for_loop_niter_p
you proved that the IV cannot wrap. You compute this "period"
as (max-val-of-IV-type - initial-IV-value + IV-step - 1) / IV-step,
that is, after how many iterations the IV will have overflowed
(testcase that covers the corner cases to make sure you didn't introduce
an off-by-one error here?). I think the naming of the functions
is unfortunate here (max_nowrap_iter?).
Btw, you do not seem to handle a negative IV-step in any special
way even though that would wrap around zero at some point?
(if step is always the same type as the IV you are of course fine
as it will be never negative that way - but you'll pessimize things
then because those wrappings are not really wrappings?)
And btw, in period_greater_niter_exit I don't see why you need to
check the overall max iterations for the non-constant niter case.
Isn't the upper bound recorded for the particular exit enough?
You should not use TYPE_MAX_VALUE anywhere but only
the maximum value based on TYPE_PRECISION.
+ else if (TREE_CODE (mbz) == EQ_EXPR)
+ {
+ /* Check whether may_be_zero is in below three forms:
+ 1) b' == TYPE_MAX_VALUE (TREE_TYPE (b'))
+ where b' is of type nit_type. The expression could be
+ folded from "b' + 1 < 1". In this case, A is "0" and B
+ is "b' + 1".
...
this looks like a separate "feature" - please commit it separately
(same comment about TYPE_MAX_VALUE applies).
/* Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not
- overflow. */
- offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
- cand->iv->step,
- fold_convert (TREE_TYPE (cand->iv->step), a));
+ overflow. It is uncessary to build offset when A equals to ZERO. */
+ if (a != integer_zero_node)
+ offset = fold_build2 (MULT_EXPR, TREE_TYPE (cand->iv->step),
+ cand->iv->step,
+ fold_convert (TREE_TYPE (cand->iv->step), a));
+ else
+ offset = a;
+
looks like premature optimization to me? It should use
integer_zerop (a) anyway.
This is the case iff the period of the induction variable is greater
than the number of iterations for which the exit condition is true. */
period = iv_period (cand->iv);
+ if (!period_greater_niter_exit (data, use, cand, period, desc))
+ return false;
huh, and there is already a iv_period function...? (which doesn't
take into account the IV initial value - but at least it's a true
"period")
Overall this looks good, but the wide-int use at the beginning looks
odd to me and I'd like you not use TYPE_MAX_VALUE.
Richard.
> 2014-09-30 Bin Cheng <bin.ch...@arm.com>
>
> * tree-ssa-loop-ivopts.c (iv_nowrap_period)
> (nowrap_cand_for_loop_niter_p): New functions.
> (period_greater_niter_exit): New function refactored from
> may_eliminate_iv.
> (difference_cannot_overflow_p): Handle zero offset.
> (iv_elimination_compare_lt): New parameter. Check wrapping
> behavior for candidate of wrapping type. Handle folded forms
> of may_be_zero expression.
> (may_eliminate_iv): Call period_greater_niter_exit. Pass new
> argument for iv_elimination_compare_lt.
>
> gcc/testsuite/ChangeLog
> 2014-09-30 Bin Cheng <bin.ch...@arm.com>
>
> * gcc.dg/tree-ssa/ivopts-lt-3.c: New test.
> * gcc.dg/tree-ssa/ivopts-lt-4.c: New test.
