[PATCH] tree-optimization/102131 - fix niter analysis wrt overflow
Richard Biener
rguenther@suse.de
Mon Jan 24 12:11:30 GMT 2022
This fixes the overflow issues seen with analyzing
BASE0 + STEP0 cmp BASE1 + STEP1 as BASE0 + STEP0 - STEP1 cmp BASE1
by following the logic we have when simplifying comparisons.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
I've built SPEC 2017 with extra statistics and in all of it there
are 518 cases where the new condition triggers (that's of course
usually multiple times per actual loop). I don't have the number
of cases where IV analysis failed upon further analysis with the
old logic though. Those 518 cases are out of a total number of
4744090 cases that run into the simplification out of which 4722153
return successfully from number_of_iterations_cond. 619 cases fail
with the old test (non-wrapping IVs and constant step).
Based on this analysis I have pushed this change now.
Richard.
2022-01-24 Richard Biener <rguenther@suse.de>
Jiufu Guo <guojiufu@linux.ibm.com>
PR tree-optimization/100740
PR tree-optimization/101508
PR tree-optimization/101972
PR tree-optimization/102131
* tree-ssa-loop-niter.cc (): Properly constrain
BASE0 + STEP0 cmp BASE1 + STEP1 to BASE0 + STEP0 - STEP1 cmp BASE1
transform.
* gcc.dg/torture/pr100740.c: New testcase.
* gcc.dg/torture/pr101508.c: Likewise.
* gcc.dg/torture/pr101972.c: Likewise.
* gcc.dg/torture/pr102131-1.c: Likewise.
* gcc.dg/torture/pr102131-2.c: Likewise.
* gcc.dg/torture/pr102131-3.c: Likewise.
* gcc.dg/torture/pr102131-4.c: Likewise.
---
gcc/testsuite/gcc.dg/torture/pr100740.c | 12 +++++++
gcc/testsuite/gcc.dg/torture/pr101508.c | 13 ++++++++
gcc/testsuite/gcc.dg/torture/pr101972.c | 39 +++++++++++++++++++++++
gcc/testsuite/gcc.dg/torture/pr102131-1.c | 16 ++++++++++
gcc/testsuite/gcc.dg/torture/pr102131-2.c | 15 +++++++++
gcc/testsuite/gcc.dg/torture/pr102131-3.c | 11 +++++++
gcc/testsuite/gcc.dg/torture/pr102131-4.c | 15 +++++++++
gcc/tree-ssa-loop-niter.cc | 29 +++++++++++------
8 files changed, 141 insertions(+), 9 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/torture/pr100740.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr101508.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr101972.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr102131-1.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr102131-2.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr102131-3.c
create mode 100644 gcc/testsuite/gcc.dg/torture/pr102131-4.c
diff --git a/gcc/testsuite/gcc.dg/torture/pr100740.c b/gcc/testsuite/gcc.dg/torture/pr100740.c
new file mode 100644
index 00000000000..a85855ebe18
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr100740.c
@@ -0,0 +1,12 @@
+/* { dg-do run } */
+
+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/testsuite/gcc.dg/torture/pr101508.c b/gcc/testsuite/gcc.dg/torture/pr101508.c
new file mode 100644
index 00000000000..e1cb2645a31
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr101508.c
@@ -0,0 +1,13 @@
+/* { dg-do run } */
+
+int
+main ()
+{
+ unsigned i;
+ for (i = 0; i < 3; ++i)
+ {
+ if (i > i * 2)
+ __builtin_abort ();
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr101972.c b/gcc/testsuite/gcc.dg/torture/pr101972.c
new file mode 100644
index 00000000000..3adb4828ea5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr101972.c
@@ -0,0 +1,39 @@
+/* { dg-do run } */
+/* { dg-require-effective-target int32plus } */
+
+int a, b, c, d, f;
+static short e = 63891;
+char g = 30;
+unsigned h(int i, int j) { return i << j; }
+int *l(int *);
+void m()
+{
+ a = 0;
+ for (; a >= 0; a--)
+ {
+ int *k = &b;
+ *k = e < 0;
+ }
+ c = b;
+ l(&c);
+}
+int *l(int *i)
+{
+ d = 2;
+ for (; d <= 6; d++)
+ {
+ if (h(d, *i) <= d)
+ ;
+ else
+ continue;
+ g = 0;
+ return &f;
+ }
+ return (void *)0;
+}
+int main()
+{
+ m();
+ if (g != 30)
+ __builtin_abort ();
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr102131-1.c b/gcc/testsuite/gcc.dg/torture/pr102131-1.c
new file mode 100644
index 00000000000..5ff576d8634
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr102131-1.c
@@ -0,0 +1,16 @@
+/* { dg-do run } */
+
+int a;
+int main()
+{
+ unsigned b = 0;
+ int c = 1;
+ for (; b < 3; b++)
+ {
+ while (c < b)
+ __builtin_abort ();
+ for (a = 0; a < 3; a++)
+ c++;
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr102131-2.c b/gcc/testsuite/gcc.dg/torture/pr102131-2.c
new file mode 100644
index 00000000000..830c72c23d9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr102131-2.c
@@ -0,0 +1,15 @@
+/* { dg-do run } */
+
+int a;
+int main()
+{
+ unsigned b = 0;
+ int c = 1;
+ for (;b < 3; b++)
+ {
+ if (c < b)
+ __builtin_abort ();
+ c+=3;
+ }
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr102131-3.c b/gcc/testsuite/gcc.dg/torture/pr102131-3.c
new file mode 100644
index 00000000000..aed10c973e6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr102131-3.c
@@ -0,0 +1,11 @@
+/* { dg-do run } */
+
+int a;
+int main()
+{
+ unsigned b = 0;
+ for (a = 2; a < 8; a += 2)
+ if (++b > a)
+ __builtin_abort();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/torture/pr102131-4.c b/gcc/testsuite/gcc.dg/torture/pr102131-4.c
new file mode 100644
index 00000000000..c63c08b2137
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/torture/pr102131-4.c
@@ -0,0 +1,15 @@
+/* { dg-do run } */
+/* { dg-require-effective-target int32plus } */
+
+unsigned a;
+int main()
+{
+ unsigned b = 1;
+ for (; b < 4; b++) {
+ a = (a ^ 2000000000) * -b;
+ if (b > a)
+ __builtin_abort ();
+ a = 3000000000;
+ }
+ return 0;
+}
diff --git a/gcc/tree-ssa-loop-niter.cc b/gcc/tree-ssa-loop-niter.cc
index 21cc257c91b..747d631149b 100644
--- a/gcc/tree-ssa-loop-niter.cc
+++ b/gcc/tree-ssa-loop-niter.cc
@@ -1903,17 +1903,28 @@ number_of_iterations_cond (class loop *loop,
tree step = fold_binary_to_constant (MINUS_EXPR, step_type,
iv0->step, iv1->step);
- /* 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;
+ /* For code other than NE_EXPR we have to ensure moving the evolution
+ of IV1 to that of IV0 does not introduce overflow. */
+ if (TREE_CODE (step) != INTEGER_CST
+ || !iv0->no_overflow || !iv1->no_overflow)
+ {
+ if (code != NE_EXPR)
+ return false;
+ iv0->no_overflow = false;
+ }
+ /* If the new step of IV0 has changed sign or is of greater
+ magnitude then we do not know whether IV0 does overflow
+ and thus the transform is not valid for code other than NE_EXPR */
+ else if (tree_int_cst_sign_bit (step) != tree_int_cst_sign_bit (iv0->step)
+ || wi::gtu_p (wi::abs (wi::to_widest (step)),
+ wi::abs (wi::to_widest (iv0->step))))
+ {
+ if (code != NE_EXPR)
+ return false;
+ iv0->no_overflow = false;
+ }
iv0->step = step;
- if (!POINTER_TYPE_P (type))
- iv0->no_overflow = false;
-
iv1->step = build_int_cst (step_type, 0);
iv1->no_overflow = true;
}
--
2.31.1
More information about the Gcc-patches
mailing list