Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
On Fri, Jul 2, 2021 at 3:37 AM Bin.Cheng wrote:
>
> On Thu, Jul 1, 2021 at 8:19 PM Richard Biener
> wrote:
> >
> > On Mon, Jun 7, 2021 at 4:35 PM Richard Biener
> > wrote:
> > >
> > > On Sun, Jun 6, 2021 at 12:01 PM Bin.Cheng wrote:
> > > >
> > > > On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
> > > > wrote:
> > > > >
> > > > > On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> > > > > wrote:
> > > > > >
> > > > > > Hi,
> > > > > > As described in patch summary, this fixes the wrong code issue by
> > > > > > adding overflow-ness
> > > > > > check for iv1.step - iv2.step.
> > > > > >
> > > > > > Bootstrap and test on x86_64. Any comments?
> > > > >
> > > > > + bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
> > > > > + if (wrap_p)
> > > > > + {
> > > > > + tree t = fold_binary_to_constant (GE_EXPR, step_type,
> > > > > + iv0->step, iv1->step);
> > > > > + wrap_p = integer_zerop (t);
> > > > > + }
> > > > >
> > > > > I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
> > > > > that's only relevant for expressions written by the user - we're
> > > > > computing iv0.step - iv1.step
> > > > > which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may
> > > > > not
> > > > > even generate this expression then!). So I think we have to do sth
> > > > > like
> > > > >
> > > > >/* If the iv0->step - iv1->step wraps, fail. */
> > > > >if (!operand_equal_p (iv0->step, iv1->step)
> > > > >&& (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
> > > > > (iv1->step) != INTEGER_CST)
> > > > >&& !wi::gt (wi::to_widest (iv0->step), wi::to_widest
> > > > > (iv1->step))
> > > > > return false;
> > > > >
> > > > > which only handles equality and all integer constant steps. You could
> > > > Thanks for the suggestion. I realized that we have LE/LT/NE
> > > > conditions here, and for LE/LT what we need to check is iv0/iv1
> > > > converge to each other, rather than diverge. Also steps here can only
> > > > be constants, so there is no need to use range information.
> > >
> > > Ah, that simplifies things.
> > >
> > > + if (tree_int_cst_lt (iv0->step, iv1->step))
> > > + return false;
> > >
> > > so it looks to me that iv?->step can be negative which means we should
> > > verify that abs(iv0->step - iv1->step) <= abs (iv0->step), correct?
> > >
> > >tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
> > >iv0->step, iv1->step);
> > > ...
> > > + if (TREE_CODE (step) != INTEGER_CST)
> > > + return false;
> > >
> > > note fold_binary_to_constant will return NULL if the result is not
> > > TREE_CONSTANT (which would also include symbolic constants
> > > like - ). It wasn't checked before, of course but since we're
> > > touching the code we might very well be checking for NULL step ...
> > > (or assert it is not for documentation purposes).
> > >
> > > That said, if iv0->step and iv1->step are known INTEGER_CSTs
> > > (I think they indeed are given the constraints we impose on
> > > simple_iv_with_niters).
> > >
> > > That said, with just a quick look again it looks to me the
> > > IV1 {<=,<} IV2 transform to IV1 - IV2step {<=,<} IV2base
> > > is OK whenever the effective step magnitude on the IV1'
> > > decreases, thus abs(IV1.step - IV2.step) <= abs(IV1.step)
> > > since then IV1 is still guaranteed to not overflow. But
> > > for example {0, +, 1} and {10, -, 1} also converge if the
> > > number of iterations is less than 10 but they would not pass
> > > this criteria. So I'm not sure "convergence" is a good wording
> > > here - but maybe I'm missing some critical piece of understanding
> > > here.
> > >
> > > But in any case it looks like we're on the right track ;)
> >
> > Just to pick up things where we left them (and seeing the patch to
> > unti-wrap which reminded me), I've digged in myself a bit and
> > came to the following conclusion.
> >
> > The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only
> > valid if b0 + s0 - s1 does not wrap which we can only ensure
> > by ensuring that b0 + s0 and b1 + s1 do not wrap (which we
> > already check) but also - what we're missing - that (s0 - s1)
> > makes b0 still evolve in the same direction (thus s0-s1 has the
> > same sign as s0) and that its magnitude is less that that of s0.
> >
> > Extra cases could be handled if we have an upper bound for
> > the number of iterations from other sources, not sure if that's
> > worth checking.
> >
> > Thus I am testing the attached now.
> >
> > Hope you don't mind - and I of course welcome any comments.
> Oh, not at all. Your help on these issues are greatly appreciated.
>
> As for the change:
>
> > + if (tree_int_cst_sign_bit (iv0->step) != tree_int_cst_sign_bit
> > (step)
> > + || wi::geu_p (wi::abs (wi::to_wide
Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
On Thu, Jul 1, 2021 at 8:19 PM Richard Biener
wrote:
>
> On Mon, Jun 7, 2021 at 4:35 PM Richard Biener
> wrote:
> >
> > On Sun, Jun 6, 2021 at 12:01 PM Bin.Cheng wrote:
> > >
> > > On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
> > > wrote:
> > > >
> > > > On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> > > > wrote:
> > > > >
> > > > > Hi,
> > > > > As described in patch summary, this fixes the wrong code issue by
> > > > > adding overflow-ness
> > > > > check for iv1.step - iv2.step.
> > > > >
> > > > > Bootstrap and test on x86_64. Any comments?
> > > >
> > > > + bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
> > > > + if (wrap_p)
> > > > + {
> > > > + tree t = fold_binary_to_constant (GE_EXPR, step_type,
> > > > + iv0->step, iv1->step);
> > > > + wrap_p = integer_zerop (t);
> > > > + }
> > > >
> > > > I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
> > > > that's only relevant for expressions written by the user - we're
> > > > computing iv0.step - iv1.step
> > > > which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not
> > > > even generate this expression then!). So I think we have to do sth like
> > > >
> > > >/* If the iv0->step - iv1->step wraps, fail. */
> > > >if (!operand_equal_p (iv0->step, iv1->step)
> > > >&& (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
> > > > (iv1->step) != INTEGER_CST)
> > > >&& !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step))
> > > > return false;
> > > >
> > > > which only handles equality and all integer constant steps. You could
> > > Thanks for the suggestion. I realized that we have LE/LT/NE
> > > conditions here, and for LE/LT what we need to check is iv0/iv1
> > > converge to each other, rather than diverge. Also steps here can only
> > > be constants, so there is no need to use range information.
> >
> > Ah, that simplifies things.
> >
> > + if (tree_int_cst_lt (iv0->step, iv1->step))
> > + return false;
> >
> > so it looks to me that iv?->step can be negative which means we should
> > verify that abs(iv0->step - iv1->step) <= abs (iv0->step), correct?
> >
> >tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
> >iv0->step, iv1->step);
> > ...
> > + if (TREE_CODE (step) != INTEGER_CST)
> > + return false;
> >
> > note fold_binary_to_constant will return NULL if the result is not
> > TREE_CONSTANT (which would also include symbolic constants
> > like - ). It wasn't checked before, of course but since we're
> > touching the code we might very well be checking for NULL step ...
> > (or assert it is not for documentation purposes).
> >
> > That said, if iv0->step and iv1->step are known INTEGER_CSTs
> > (I think they indeed are given the constraints we impose on
> > simple_iv_with_niters).
> >
> > That said, with just a quick look again it looks to me the
> > IV1 {<=,<} IV2 transform to IV1 - IV2step {<=,<} IV2base
> > is OK whenever the effective step magnitude on the IV1'
> > decreases, thus abs(IV1.step - IV2.step) <= abs(IV1.step)
> > since then IV1 is still guaranteed to not overflow. But
> > for example {0, +, 1} and {10, -, 1} also converge if the
> > number of iterations is less than 10 but they would not pass
> > this criteria. So I'm not sure "convergence" is a good wording
> > here - but maybe I'm missing some critical piece of understanding
> > here.
> >
> > But in any case it looks like we're on the right track ;)
>
> Just to pick up things where we left them (and seeing the patch to
> unti-wrap which reminded me), I've digged in myself a bit and
> came to the following conclusion.
>
> The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only
> valid if b0 + s0 - s1 does not wrap which we can only ensure
> by ensuring that b0 + s0 and b1 + s1 do not wrap (which we
> already check) but also - what we're missing - that (s0 - s1)
> makes b0 still evolve in the same direction (thus s0-s1 has the
> same sign as s0) and that its magnitude is less that that of s0.
>
> Extra cases could be handled if we have an upper bound for
> the number of iterations from other sources, not sure if that's
> worth checking.
>
> Thus I am testing the attached now.
>
> Hope you don't mind - and I of course welcome any comments.
Oh, not at all. Your help on these issues are greatly appreciated.
As for the change:
> + if (tree_int_cst_sign_bit (iv0->step) != tree_int_cst_sign_bit
> (step)
> + || wi::geu_p (wi::abs (wi::to_wide (step)),
> + wi::abs (wi::to_wide (iv0->step
It returns false on condition "{base, 5}_iv0 < {base, -1}_iv1", but
this is like the "convergence" case I mentioned and could be analyzed?
Thanks,
bin
> + return false;
> + }
Thanks,
bin
>
> Thanks,
> Richard.
>
>
Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
On Mon, Jun 7, 2021 at 4:35 PM Richard Biener
wrote:
>
> On Sun, Jun 6, 2021 at 12:01 PM Bin.Cheng wrote:
> >
> > On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
> > wrote:
> > >
> > > On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> > > wrote:
> > > >
> > > > Hi,
> > > > As described in patch summary, this fixes the wrong code issue by
> > > > adding overflow-ness
> > > > check for iv1.step - iv2.step.
> > > >
> > > > Bootstrap and test on x86_64. Any comments?
> > >
> > > + bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
> > > + if (wrap_p)
> > > + {
> > > + tree t = fold_binary_to_constant (GE_EXPR, step_type,
> > > + iv0->step, iv1->step);
> > > + wrap_p = integer_zerop (t);
> > > + }
> > >
> > > I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
> > > that's only relevant for expressions written by the user - we're
> > > computing iv0.step - iv1.step
> > > which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not
> > > even generate this expression then!). So I think we have to do sth like
> > >
> > >/* If the iv0->step - iv1->step wraps, fail. */
> > >if (!operand_equal_p (iv0->step, iv1->step)
> > >&& (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
> > > (iv1->step) != INTEGER_CST)
> > >&& !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step))
> > > return false;
> > >
> > > which only handles equality and all integer constant steps. You could
> > Thanks for the suggestion. I realized that we have LE/LT/NE
> > conditions here, and for LE/LT what we need to check is iv0/iv1
> > converge to each other, rather than diverge. Also steps here can only
> > be constants, so there is no need to use range information.
>
> Ah, that simplifies things.
>
> + if (tree_int_cst_lt (iv0->step, iv1->step))
> + return false;
>
> so it looks to me that iv?->step can be negative which means we should
> verify that abs(iv0->step - iv1->step) <= abs (iv0->step), correct?
>
>tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
>iv0->step, iv1->step);
> ...
> + if (TREE_CODE (step) != INTEGER_CST)
> + return false;
>
> note fold_binary_to_constant will return NULL if the result is not
> TREE_CONSTANT (which would also include symbolic constants
> like - ). It wasn't checked before, of course but since we're
> touching the code we might very well be checking for NULL step ...
> (or assert it is not for documentation purposes).
>
> That said, if iv0->step and iv1->step are known INTEGER_CSTs
> (I think they indeed are given the constraints we impose on
> simple_iv_with_niters).
>
> That said, with just a quick look again it looks to me the
> IV1 {<=,<} IV2 transform to IV1 - IV2step {<=,<} IV2base
> is OK whenever the effective step magnitude on the IV1'
> decreases, thus abs(IV1.step - IV2.step) <= abs(IV1.step)
> since then IV1 is still guaranteed to not overflow. But
> for example {0, +, 1} and {10, -, 1} also converge if the
> number of iterations is less than 10 but they would not pass
> this criteria. So I'm not sure "convergence" is a good wording
> here - but maybe I'm missing some critical piece of understanding
> here.
>
> But in any case it looks like we're on the right track ;)
Just to pick up things where we left them (and seeing the patch to
unti-wrap which reminded me), I've digged in myself a bit and
came to the following conclusion.
The b0 + s0 < b1 + s1 -> b0 + s0 - s1 < b1 transform is only
valid if b0 + s0 - s1 does not wrap which we can only ensure
by ensuring that b0 + s0 and b1 + s1 do not wrap (which we
already check) but also - what we're missing - that (s0 - s1)
makes b0 still evolve in the same direction (thus s0-s1 has the
same sign as s0) and that its magnitude is less that that of s0.
Extra cases could be handled if we have an upper bound for
the number of iterations from other sources, not sure if that's
worth checking.
Thus I am testing the attached now.
Hope you don't mind - and I of course welcome any comments.
Thanks,
Richard.
> Thanks,
> Richard.
>
> > > also use ranges
> > > like
> > >
> > > wide_int min0, max0, min1, max1;
> > > if (!operand_equal_p (iv->step, iv1->step)
> > > && (determine_value_range (iv0->step, , ) != VR_RANGE
> > > || determine_value_range (iv1->step, , ) !=
> > > VR_RANGE
> > > || !wi::ge (min0, max1)))
> > >return false;
> > >
> > > Note I'm not sure why
> > >
> > >iv0->step = step;
> > >if (!POINTER_TYPE_P (type))
> > > iv0->no_overflow = false;
> > I don't exactly remember, this was added sometime when no_overflow was
> > introduced. Note we only do various checks for non NE_EXPR so the
> > step isn't always less in absolute value? I will check if we should
> > reset it in all cases.
Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
On Sun, Jun 6, 2021 at 12:01 PM Bin.Cheng wrote:
>
> On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
> wrote:
> >
> > On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> > wrote:
> > >
> > > Hi,
> > > As described in patch summary, this fixes the wrong code issue by adding
> > > overflow-ness
> > > check for iv1.step - iv2.step.
> > >
> > > Bootstrap and test on x86_64. Any comments?
> >
> > + bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
> > + if (wrap_p)
> > + {
> > + tree t = fold_binary_to_constant (GE_EXPR, step_type,
> > + iv0->step, iv1->step);
> > + wrap_p = integer_zerop (t);
> > + }
> >
> > I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
> > that's only relevant for expressions written by the user - we're
> > computing iv0.step - iv1.step
> > which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not
> > even generate this expression then!). So I think we have to do sth like
> >
> >/* If the iv0->step - iv1->step wraps, fail. */
> >if (!operand_equal_p (iv0->step, iv1->step)
> >&& (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
> > (iv1->step) != INTEGER_CST)
> >&& !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step))
> > return false;
> >
> > which only handles equality and all integer constant steps. You could
> Thanks for the suggestion. I realized that we have LE/LT/NE
> conditions here, and for LE/LT what we need to check is iv0/iv1
> converge to each other, rather than diverge. Also steps here can only
> be constants, so there is no need to use range information.
Ah, that simplifies things.
+ if (tree_int_cst_lt (iv0->step, iv1->step))
+ return false;
so it looks to me that iv?->step can be negative which means we should
verify that abs(iv0->step - iv1->step) <= abs (iv0->step), correct?
tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
iv0->step, iv1->step);
...
+ if (TREE_CODE (step) != INTEGER_CST)
+ return false;
note fold_binary_to_constant will return NULL if the result is not
TREE_CONSTANT (which would also include symbolic constants
like - ). It wasn't checked before, of course but since we're
touching the code we might very well be checking for NULL step ...
(or assert it is not for documentation purposes).
That said, if iv0->step and iv1->step are known INTEGER_CSTs
(I think they indeed are given the constraints we impose on
simple_iv_with_niters).
That said, with just a quick look again it looks to me the
IV1 {<=,<} IV2 transform to IV1 - IV2step {<=,<} IV2base
is OK whenever the effective step magnitude on the IV1'
decreases, thus abs(IV1.step - IV2.step) <= abs(IV1.step)
since then IV1 is still guaranteed to not overflow. But
for example {0, +, 1} and {10, -, 1} also converge if the
number of iterations is less than 10 but they would not pass
this criteria. So I'm not sure "convergence" is a good wording
here - but maybe I'm missing some critical piece of understanding
here.
But in any case it looks like we're on the right track ;)
Thanks,
Richard.
> > also use ranges
> > like
> >
> > wide_int min0, max0, min1, max1;
> > if (!operand_equal_p (iv->step, iv1->step)
> > && (determine_value_range (iv0->step, , ) != VR_RANGE
> > || determine_value_range (iv1->step, , ) != VR_RANGE
> > || !wi::ge (min0, max1)))
> >return false;
> >
> > Note I'm not sure why
> >
> >iv0->step = step;
> >if (!POINTER_TYPE_P (type))
> > iv0->no_overflow = false;
> I don't exactly remember, this was added sometime when no_overflow was
> introduced. Note we only do various checks for non NE_EXPR so the
> step isn't always less in absolute value? I will check if we should
> reset it in all cases.
>
> Patch updated. test ongoing.
>
> Thanks,
> bin
> >
> > here the no_overflow reset does not happen for pointer types? Or
> > rather why does
> > it happen at all? Don't we strictly make the step less in absolute value?
> >
> > > Thanks,
> > > bin
Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
wrote:
>
> On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> wrote:
> >
> > Hi,
> > As described in patch summary, this fixes the wrong code issue by adding
> > overflow-ness
> > check for iv1.step - iv2.step.
> >
> > Bootstrap and test on x86_64. Any comments?
>
> + bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
> + if (wrap_p)
> + {
> + tree t = fold_binary_to_constant (GE_EXPR, step_type,
> + iv0->step, iv1->step);
> + wrap_p = integer_zerop (t);
> + }
>
> I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
> that's only relevant for expressions written by the user - we're
> computing iv0.step - iv1.step
> which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not
> even generate this expression then!). So I think we have to do sth like
>
>/* If the iv0->step - iv1->step wraps, fail. */
>if (!operand_equal_p (iv0->step, iv1->step)
>&& (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
> (iv1->step) != INTEGER_CST)
>&& !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step))
> return false;
>
> which only handles equality and all integer constant steps. You could
Thanks for the suggestion. I realized that we have LE/LT/NE
conditions here, and for LE/LT what we need to check is iv0/iv1
converge to each other, rather than diverge. Also steps here can only
be constants, so there is no need to use range information.
> also use ranges
> like
>
> wide_int min0, max0, min1, max1;
> if (!operand_equal_p (iv->step, iv1->step)
> && (determine_value_range (iv0->step, , ) != VR_RANGE
> || determine_value_range (iv1->step, , ) != VR_RANGE
> || !wi::ge (min0, max1)))
>return false;
>
> Note I'm not sure why
>
>iv0->step = step;
>if (!POINTER_TYPE_P (type))
> iv0->no_overflow = false;
I don't exactly remember, this was added sometime when no_overflow was
introduced. Note we only do various checks for non NE_EXPR so the
step isn't always less in absolute value? I will check if we should
reset it in all cases.
Patch updated. test ongoing.
Thanks,
bin
>
> here the no_overflow reset does not happen for pointer types? Or
> rather why does
> it happen at all? Don't we strictly make the step less in absolute value?
>
> > Thanks,
> > bin
From 395dd6595cabebb7fd3e71a5fbfe84544d598608 Mon Sep 17 00:00:00 2001
Author: Bin Cheng
Date: Fri, 28 May 2021 16:49:54 +0800
Subject: [PATCH] Simplify exit cond comparing two IVs only if they converge.
We should also check that iv1.step >= iv2.step so that the two IVs
converge to each other under comparison condition LE_EXPR/LT_EXPR.
gcc:
PR tree-optimization/100740
* tree-ssa-loop-niter.c (number_of_iterations_cond): Check
IVs converge or not.
gcc/testsuite:
* gcc.c-torture/execute/pr100740.c
---
.../gcc.c-torture/execute/pr100740.c | 11 ++
gcc/tree-ssa-loop-niter.c | 20 +--
2 files changed, 25 insertions(+), 6 deletions(-)
create mode 100644 gcc/testsuite/gcc.c-torture/execute/pr100740.c
diff --git a/gcc/testsuite/gcc.c-torture/execute/pr100740.c
b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
new file mode 100644
index 000..8fcdaffef3b
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/execute/pr100740.c
@@ -0,0 +1,11 @@
+/* PR tree-optimization/100740 */
+
+unsigned a, b;
+int main() {
+ unsigned c = 0;
+ for (a = 0; a < 2; a++)
+for (b = 0; b < 2; b++)
+ if (++c < a)
+__builtin_abort ();
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
index 325bd978609..6240084782a 100644
--- a/gcc/tree-ssa-loop-niter.c
+++ b/gcc/tree-ssa-loop-niter.c
@@ -1782,7 +1782,9 @@ number_of_iterations_cond (class loop *loop,
provided that either below condition is satisfied:
a) the test is NE_EXPR;
- b) iv0.step - iv1.step is integer and iv0/iv1 don't overflow.
+ b) iv0.step and iv1.step are integers and:
+ - iv0 and iv1 don't overflow.
+ - iv0 and iv1 converge to each other, under cond LE_EXPR/LT_EXPR.
This rarely occurs in practice, but it is simple enough to manage. */
if (!integer_zerop (iv0->step) && !integer_zerop (iv1->step))
@@ -1790,14 +1792,20 @@ number_of_iterations_cond (class loop *loop,
tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
iv0->step, iv1->step);
+ if (code != NE_EXPR)
+ {
+ if (TREE_CODE (step) != INTEGER_CST)
+ return false;
+
+ if (!iv0->no_overflow || !iv1->no_overflow)
+ return false;
+
+ if (tree_int_cst_lt (iv0->step, iv1->step))
+ return false;
+ }
Re: [PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
wrote:
>
> Hi,
> As described in patch summary, this fixes the wrong code issue by adding
> overflow-ness
> check for iv1.step - iv2.step.
>
> Bootstrap and test on x86_64. Any comments?
+ bool wrap_p = TYPE_OVERFLOW_WRAPS (step_type);
+ if (wrap_p)
+ {
+ tree t = fold_binary_to_constant (GE_EXPR, step_type,
+ iv0->step, iv1->step);
+ wrap_p = integer_zerop (t);
+ }
I think we can't use TYPE_OVERFLOW_WRAPS/TYPE_OVERFLOW_UNDEFINED since
that's only relevant for expressions written by the user - we're
computing iv0.step - iv1.step
which can even overflow when TYPE_OVERFLOW_UNDEFINED (in fact we may not
even generate this expression then!). So I think we have to do sth like
/* If the iv0->step - iv1->step wraps, fail. */
if (!operand_equal_p (iv0->step, iv1->step)
&& (TREE_CODE (iv0->step) != INTEGER_CST || TREE_CODE
(iv1->step) != INTEGER_CST)
&& !wi::gt (wi::to_widest (iv0->step), wi::to_widest (iv1->step))
return false;
which only handles equality and all integer constant steps. You could
also use ranges
like
wide_int min0, max0, min1, max1;
if (!operand_equal_p (iv->step, iv1->step)
&& (determine_value_range (iv0->step, , ) != VR_RANGE
|| determine_value_range (iv1->step, , ) != VR_RANGE
|| !wi::ge (min0, max1)))
return false;
Note I'm not sure why
iv0->step = step;
if (!POINTER_TYPE_P (type))
iv0->no_overflow = false;
here the no_overflow reset does not happen for pointer types? Or
rather why does
it happen at all? Don't we strictly make the step less in absolute value?
> Thanks,
> bin
[PATCH PR100740]Fix overflow check in simplifying exit cond comparing two IVs.
Hi, As described in patch summary, this fixes the wrong code issue by adding overflow-ness check for iv1.step - iv2.step. Bootstrap and test on x86_64. Any comments? Thanks, bin pr100740-20210525.txt Description: Binary data
