From 4f75d60893e092cffcbe422825ce4dc092d3fb9e Mon Sep 17 00:00:00 2001 From: Tom de Vries Date: Tue, 30 Jun 2015 08:35:57 +0000 Subject: [PATCH] Use max_loop_iterations in transform_to_exit_first_loop_alt 2015-06-30 Tom de Vries PR tree-optimization/66652 * tree-parloops.c (try_transform_to_exit_first_loop_alt): Use max_loop_iterations to determine if nit + 1 overflows. * testsuite/libgomp.c/parloops-exit-first-loop-alt-3.c (f): Rewrite using restrict pointers. (main): Add arguments to calls to f. * testsuite/libgomp.c/parloops-exit-first-loop-alt.c: Same. * gcc.dg/parloops-exit-first-loop-alt-pr66652.c: New test. * gcc.dg/parloops-exit-first-loop-alt-3.c (f): Rewrite using restrict pointers. * gcc.dg/parloops-exit-first-loop-alt.c: Same. From-SVN: r225162 --- gcc/ChangeLog | 6 ++++ gcc/testsuite/ChangeLog | 8 +++++ .../gcc.dg/parloops-exit-first-loop-alt-3.c | 2 +- .../parloops-exit-first-loop-alt-pr66652.c | 31 +++++++++++++++++++ .../gcc.dg/parloops-exit-first-loop-alt.c | 19 +++++------- gcc/tree-parloops.c | 31 +++++++++++++++++++ libgomp/ChangeLog | 8 +++++ .../parloops-exit-first-loop-alt-3.c | 4 +-- .../libgomp.c/parloops-exit-first-loop-alt.c | 5 +-- 9 files changed, 97 insertions(+), 17 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-pr66652.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 00954b1ef08..9b8c7cff399 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2015-06-30 Tom de Vries + + PR tree-optimization/66652 + * tree-parloops.c (try_transform_to_exit_first_loop_alt): Use + max_loop_iterations to determine if nit + 1 overflows. + 2015-06-30 Richard Biener * tree-vrp.c (register_edge_assert_for_2): Also register diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 9c2f20b2c72..f249a7d7ded 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,11 @@ +2015-06-30 Tom de Vries + + PR tree-optimization/66652 + * gcc.dg/parloops-exit-first-loop-alt-pr66652.c: New test. + * gcc.dg/parloops-exit-first-loop-alt-3.c (f): Rewrite using restrict + pointers. + * gcc.dg/parloops-exit-first-loop-alt.c: Same. + 2015-06-29 Paolo Carlini PR c++/65977 diff --git a/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-3.c b/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-3.c index b0fde372a14..fec53a19628 100644 --- a/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-3.c +++ b/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-3.c @@ -7,7 +7,7 @@ unsigned int *a; unsigned int -f (unsigned int n) +f (unsigned int n, unsigned int *__restrict__ a) { int i; unsigned int sum = 1; diff --git a/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-pr66652.c b/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-pr66652.c new file mode 100644 index 00000000000..2ea097d06f9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt-pr66652.c @@ -0,0 +1,31 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target pthread } */ +/* { dg-options "-O2 -ftree-parallelize-loops=2 -fdump-tree-parloops" } */ + +#include +#include +#include + +unsigned int +f (unsigned int n, unsigned int sum) +{ + unsigned int i; + + i = UINT_MAX; + do + { + sum += i % 13; + i++; + } + while (i < n - 1); + + return sum; +} + +/* Four times % 13: + - once in f._loopfn.0 + - once in the parallel + - once in the low iteration count loop + - once for a peeled off last iteration following the parallel. + In other words, we want try_transform_to_exit_first_loop_alt to fail. */ +/* { dg-final { scan-tree-dump-times "(?n)% 13" 4 "parloops" } } */ diff --git a/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt.c b/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt.c index b36f01b8f8f..e088fa110b3 100644 --- a/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt.c +++ b/gcc/testsuite/gcc.dg/parloops-exit-first-loop-alt.c @@ -4,14 +4,9 @@ /* Variable bound, vector addition. */ -#define N 1000 - -unsigned int a[N]; -unsigned int b[N]; -unsigned int c[N]; - void -f (unsigned int n) +f (unsigned int n, unsigned int *__restrict__ a, unsigned int *__restrict__ b, + unsigned int *__restrict__ c) { int i; @@ -19,9 +14,9 @@ f (unsigned int n) c[i] = a[i] + b[i]; } -/* Three times three array accesses: - - three in f._loopfn.0 - - three in the parallel - - three in the low iteration count loop +/* Three times a store: + - one in f._loopfn.0 + - one in the parallel + - one in the low iteration count loop Crucially, none for a peeled off last iteration following the parallel. */ -/* { dg-final { scan-tree-dump-times "(?n)\\\[i" 9 "parloops" } } */ +/* { dg-final { scan-tree-dump-times "(?n)^ \\*_\[0-9\]*" 3 "parloops" } } */ diff --git a/gcc/tree-parloops.c b/gcc/tree-parloops.c index ec708c67ac9..21ed17b4caf 100644 --- a/gcc/tree-parloops.c +++ b/gcc/tree-parloops.c @@ -1801,8 +1801,39 @@ try_transform_to_exit_first_loop_alt (struct loop *loop, gcc_assert (TREE_CODE (nit) == SSA_NAME); + /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an + iv with base 0 and step 1 that is incremented in the latch, like this: + + : + # iv_1 = PHI <0 (preheader), iv_2 (latch)> + ... + if (iv_1 < nit) + goto ; + else + goto ; + + : + iv_2 = iv_1 + 1; + goto ; + + The range of iv_1 is [0, nit]. The latch edge is taken for + iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit. So the + number of latch executions is equal to nit. + + The function max_loop_iterations gives us the maximum number of latch + executions, so it gives us the maximum value of nit. */ + widest_int nit_max; + if (!max_loop_iterations (loop, &nit_max)) + return false; + + /* Check if nit + 1 overflows. */ + widest_int type_max = wi::to_widest (TYPE_MAXVAL (nit_type)); + if (!wi::lts_p (nit_max, type_max)) + return false; + gimple def = SSA_NAME_DEF_STMT (nit); + /* Try to find nit + 1, in the form of n in an assignment nit = n - 1. */ if (def && is_gimple_assign (def) && gimple_assign_rhs_code (def) == PLUS_EXPR) diff --git a/libgomp/ChangeLog b/libgomp/ChangeLog index a01f9b2816c..2c539b821ac 100644 --- a/libgomp/ChangeLog +++ b/libgomp/ChangeLog @@ -1,3 +1,11 @@ +2015-06-30 Tom de Vries + + PR tree-optimization/66652 + * testsuite/libgomp.c/parloops-exit-first-loop-alt-3.c (f): Rewrite + using restrict pointers. + (main): Add arguments to calls to f. + * testsuite/libgomp.c/parloops-exit-first-loop-alt.c: Same. + 2015-06-23 Andreas Tobler * configure.ac: Fix check for header . diff --git a/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt-3.c b/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt-3.c index cb5bf9cb8c5..7de1377cd56 100644 --- a/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt-3.c +++ b/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt-3.c @@ -10,7 +10,7 @@ unsigned int *a; unsigned int __attribute__((noclone,noinline)) -f (unsigned int n) +f (unsigned int n, unsigned int *__restrict__ a) { int i; unsigned int sum = 1; @@ -32,7 +32,7 @@ main (void) array[i] = i % 7; a = &array[0]; - res = f (N); + res = f (N, a); if (res != 11995) abort (); diff --git a/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt.c b/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt.c index 1c32ea33f7b..07468a9ab9e 100644 --- a/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt.c +++ b/libgomp/testsuite/libgomp.c/parloops-exit-first-loop-alt.c @@ -13,7 +13,8 @@ unsigned int b[N]; unsigned int c[N]; void __attribute__((noclone,noinline)) -f (unsigned int n) +f (unsigned int n, unsigned int *__restrict__ a, unsigned int *__restrict__ b, + unsigned int *__restrict__ c) { int i; @@ -36,7 +37,7 @@ main (void) c[k] = k * 2; } - f (N); + f (N, a, b, c); for (i = 0; i < N; i++) { -- 2.30.2