On Wed, Jun 2, 2021 at 3:28 PM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> On Tue, Jun 1, 2021 at 4:00 PM bin.cheng via Gcc-patches
> <gcc-patches@gcc.gnu.org> 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, &min0, &max0) != VR_RANGE
> || determine_value_range (iv1->step, &min1, &max1) != 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 <bin.ch...@linux.alibaba.com>
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 00000000000..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;
+ }
/* No need to check sign of the new step since below code takes care
of this well. */
- if (code != NE_EXPR
- && (TREE_CODE (step) != INTEGER_CST
- || !iv0->no_overflow || !iv1->no_overflow))
- return false;
-
iv0->step = step;
if (!POINTER_TYPE_P (type))
iv0->no_overflow = false;
--
2.19.1.6.gb485710b
