* [PATCH] Relax the requirement of reduction pattern in GCC vectorizer.
@ 2013-09-28 7:34 Cong Hou
2013-09-28 20:24 ` Xinliang David Li
2013-10-15 13:56 ` Richard Biener
0 siblings, 2 replies; 6+ messages in thread
From: Cong Hou @ 2013-09-28 7:34 UTC (permalink / raw)
To: GCC Patches; +Cc: David Li
The current GCC vectorizer requires the following pattern as a simple
reduction computation:
loop_header:
a1 = phi < a0, a2 >
a3 = ...
a2 = operation (a3, a1)
But a3 can also be defined outside of the loop. For example, the
following loop can benefit from vectorization but the GCC vectorizer
fails to vectorize it:
int foo(int v)
{
int s = 1;
++v;
for (int i = 0; i < 100000; ++i)
s *= v;
return s;
}
This patch relaxes the original requirement by also considering the
following pattern:
a3 = ...
loop_header:
a1 = phi < a0, a2 >
a2 = operation (a3, a1)
A test case is also added. The patch is tested on x86-64.
thanks,
Cong
================================
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 39c786e..45c1667 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2013-09-27 Cong Hou <congh@google.com>
+
+ * tree-vect-loop.c: Relax the requirement of the reduction
+ pattern so that one operand of the reduction operation can
+ come from outside of the loop.
+
2013-09-25 Tom Tromey <tromey@redhat.com>
* Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H)
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 09644d2..90496a2 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2013-09-27 Cong Hou <congh@google.com>
+
+ * gcc.dg/vect/vect-reduc-pattern-3.c: New test.
+
2013-09-25 Marek Polacek <polacek@redhat.com>
PR sanitizer/58413
diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
index 2871ba1..3c51c3b 100644
--- a/gcc/tree-vect-loop.c
+++ b/gcc/tree-vect-loop.c
@@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info,
gimple phi, gimple first_stmt)
a3 = ...
a2 = operation (a3, a1)
+ or
+
+ a3 = ...
+ loop_header:
+ a1 = phi < a0, a2 >
+ a2 = operation (a3, a1)
+
such that:
1. operation is commutative and associative and it is safe to
change the order of the computation (if CHECK_REDUCTION is true)
@@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info
loop_info, gimple phi,
if (def2 && def2 == phi
&& (code == COND_EXPR
|| !def1 || gimple_nop_p (def1)
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
|| (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
&& (is_gimple_assign (def1)
|| is_gimple_call (def1)
@@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info
loop_info, gimple phi,
if (def1 && def1 == phi
&& (code == COND_EXPR
|| !def2 || gimple_nop_p (def2)
+ || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
|| (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
&& (is_gimple_assign (def2)
|| is_gimple_call (def2)
diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
new file mode 100644
index 0000000..06a9416
--- /dev/null
+++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
@@ -0,0 +1,41 @@
+/* { dg-require-effective-target vect_int } */
+
+#include <stdarg.h>
+#include "tree-vect.h"
+
+#define N 10
+#define RES 1024
+
+/* A reduction pattern in which there is no data ref in
+ the loop and one operand is defined outside of the loop. */
+
+__attribute__ ((noinline)) int
+foo (int v)
+{
+ int i;
+ int result = 1;
+
+ ++v;
+ for (i = 0; i < N; i++)
+ result *= v;
+
+ return result;
+}
+
+int
+main (void)
+{
+ int res;
+
+ check_vect ();
+
+ res = foo (1);
+ if (res != RES)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
+/* { dg-final { cleanup-tree-dump "vect" } } */
+
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Relax the requirement of reduction pattern in GCC vectorizer.
2013-09-28 7:34 [PATCH] Relax the requirement of reduction pattern in GCC vectorizer Cong Hou
@ 2013-09-28 20:24 ` Xinliang David Li
2013-10-02 18:18 ` Cong Hou
2013-10-15 13:56 ` Richard Biener
1 sibling, 1 reply; 6+ messages in thread
From: Xinliang David Li @ 2013-09-28 20:24 UTC (permalink / raw)
To: Cong Hou; +Cc: GCC Patches, Richard Guenther
You can also add a test case of this form:
int foo( int t, int n, int *dst)
{
int j = 0;
int s = 1;
t++;
for (j = 0; j < n; j++)
{
dst[j] = t;
s *= t;
}
return s;
}
where without the fix the loop vectorization is missed.
David
On Fri, Sep 27, 2013 at 6:28 PM, Cong Hou <congh@google.com> wrote:
> The current GCC vectorizer requires the following pattern as a simple
> reduction computation:
>
> loop_header:
> a1 = phi < a0, a2 >
> a3 = ...
> a2 = operation (a3, a1)
>
> But a3 can also be defined outside of the loop. For example, the
> following loop can benefit from vectorization but the GCC vectorizer
> fails to vectorize it:
>
>
> int foo(int v)
> {
> int s = 1;
> ++v;
> for (int i = 0; i < 100000; ++i)
> s *= v;
> return s;
> }
>
>
> This patch relaxes the original requirement by also considering the
> following pattern:
>
>
> a3 = ...
> loop_header:
> a1 = phi < a0, a2 >
> a2 = operation (a3, a1)
>
>
> A test case is also added. The patch is tested on x86-64.
>
>
> thanks,
> Cong
>
> ================================
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 39c786e..45c1667 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2013-09-27 Cong Hou <congh@google.com>
> +
> + * tree-vect-loop.c: Relax the requirement of the reduction
> + pattern so that one operand of the reduction operation can
> + come from outside of the loop.
> +
> 2013-09-25 Tom Tromey <tromey@redhat.com>
>
> * Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H)
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 09644d2..90496a2 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,7 @@
> +2013-09-27 Cong Hou <congh@google.com>
> +
> + * gcc.dg/vect/vect-reduc-pattern-3.c: New test.
> +
> 2013-09-25 Marek Polacek <polacek@redhat.com>
>
> PR sanitizer/58413
> diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
> index 2871ba1..3c51c3b 100644
> --- a/gcc/tree-vect-loop.c
> +++ b/gcc/tree-vect-loop.c
> @@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info,
> gimple phi, gimple first_stmt)
> a3 = ...
> a2 = operation (a3, a1)
>
> + or
> +
> + a3 = ...
> + loop_header:
> + a1 = phi < a0, a2 >
> + a2 = operation (a3, a1)
> +
> such that:
> 1. operation is commutative and associative and it is safe to
> change the order of the computation (if CHECK_REDUCTION is true)
> @@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info
> loop_info, gimple phi,
> if (def2 && def2 == phi
> && (code == COND_EXPR
> || !def1 || gimple_nop_p (def1)
> + || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
> || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
> && (is_gimple_assign (def1)
> || is_gimple_call (def1)
> @@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info
> loop_info, gimple phi,
> if (def1 && def1 == phi
> && (code == COND_EXPR
> || !def2 || gimple_nop_p (def2)
> + || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
> || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
> && (is_gimple_assign (def2)
> || is_gimple_call (def2)
> diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
> gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
> new file mode 100644
> index 0000000..06a9416
> --- /dev/null
> +++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
> @@ -0,0 +1,41 @@
> +/* { dg-require-effective-target vect_int } */
> +
> +#include <stdarg.h>
> +#include "tree-vect.h"
> +
> +#define N 10
> +#define RES 1024
> +
> +/* A reduction pattern in which there is no data ref in
> + the loop and one operand is defined outside of the loop. */
> +
> +__attribute__ ((noinline)) int
> +foo (int v)
> +{
> + int i;
> + int result = 1;
> +
> + ++v;
> + for (i = 0; i < N; i++)
> + result *= v;
> +
> + return result;
> +}
> +
> +int
> +main (void)
> +{
> + int res;
> +
> + check_vect ();
> +
> + res = foo (1);
> + if (res != RES)
> + abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
> +/* { dg-final { cleanup-tree-dump "vect" } } */
> +
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Relax the requirement of reduction pattern in GCC vectorizer.
2013-09-28 20:24 ` Xinliang David Li
@ 2013-10-02 18:18 ` Cong Hou
2013-10-15 0:59 ` Cong Hou
0 siblings, 1 reply; 6+ messages in thread
From: Cong Hou @ 2013-10-02 18:18 UTC (permalink / raw)
To: GCC Patches; +Cc: Xinliang David Li, Richard Guenther
Ping.. Any comment on this patch?
thanks,
Cong
On Sat, Sep 28, 2013 at 9:34 AM, Xinliang David Li <davidxl@google.com> wrote:
> You can also add a test case of this form:
>
> int foo( int t, int n, int *dst)
> {
> int j = 0;
> int s = 1;
> t++;
> for (j = 0; j < n; j++)
> {
> dst[j] = t;
> s *= t;
> }
>
> return s;
> }
>
> where without the fix the loop vectorization is missed.
>
> David
>
> On Fri, Sep 27, 2013 at 6:28 PM, Cong Hou <congh@google.com> wrote:
>> The current GCC vectorizer requires the following pattern as a simple
>> reduction computation:
>>
>> loop_header:
>> a1 = phi < a0, a2 >
>> a3 = ...
>> a2 = operation (a3, a1)
>>
>> But a3 can also be defined outside of the loop. For example, the
>> following loop can benefit from vectorization but the GCC vectorizer
>> fails to vectorize it:
>>
>>
>> int foo(int v)
>> {
>> int s = 1;
>> ++v;
>> for (int i = 0; i < 100000; ++i)
>> s *= v;
>> return s;
>> }
>>
>>
>> This patch relaxes the original requirement by also considering the
>> following pattern:
>>
>>
>> a3 = ...
>> loop_header:
>> a1 = phi < a0, a2 >
>> a2 = operation (a3, a1)
>>
>>
>> A test case is also added. The patch is tested on x86-64.
>>
>>
>> thanks,
>> Cong
>>
>> ================================
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index 39c786e..45c1667 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,3 +1,9 @@
>> +2013-09-27 Cong Hou <congh@google.com>
>> +
>> + * tree-vect-loop.c: Relax the requirement of the reduction
>> + pattern so that one operand of the reduction operation can
>> + come from outside of the loop.
>> +
>> 2013-09-25 Tom Tromey <tromey@redhat.com>
>>
>> * Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H)
>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>> index 09644d2..90496a2 100644
>> --- a/gcc/testsuite/ChangeLog
>> +++ b/gcc/testsuite/ChangeLog
>> @@ -1,3 +1,7 @@
>> +2013-09-27 Cong Hou <congh@google.com>
>> +
>> + * gcc.dg/vect/vect-reduc-pattern-3.c: New test.
>> +
>> 2013-09-25 Marek Polacek <polacek@redhat.com>
>>
>> PR sanitizer/58413
>> diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
>> index 2871ba1..3c51c3b 100644
>> --- a/gcc/tree-vect-loop.c
>> +++ b/gcc/tree-vect-loop.c
>> @@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info,
>> gimple phi, gimple first_stmt)
>> a3 = ...
>> a2 = operation (a3, a1)
>>
>> + or
>> +
>> + a3 = ...
>> + loop_header:
>> + a1 = phi < a0, a2 >
>> + a2 = operation (a3, a1)
>> +
>> such that:
>> 1. operation is commutative and associative and it is safe to
>> change the order of the computation (if CHECK_REDUCTION is true)
>> @@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info
>> loop_info, gimple phi,
>> if (def2 && def2 == phi
>> && (code == COND_EXPR
>> || !def1 || gimple_nop_p (def1)
>> + || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
>> || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
>> && (is_gimple_assign (def1)
>> || is_gimple_call (def1)
>> @@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info
>> loop_info, gimple phi,
>> if (def1 && def1 == phi
>> && (code == COND_EXPR
>> || !def2 || gimple_nop_p (def2)
>> + || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
>> || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
>> && (is_gimple_assign (def2)
>> || is_gimple_call (def2)
>> diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>> gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>> new file mode 100644
>> index 0000000..06a9416
>> --- /dev/null
>> +++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>> @@ -0,0 +1,41 @@
>> +/* { dg-require-effective-target vect_int } */
>> +
>> +#include <stdarg.h>
>> +#include "tree-vect.h"
>> +
>> +#define N 10
>> +#define RES 1024
>> +
>> +/* A reduction pattern in which there is no data ref in
>> + the loop and one operand is defined outside of the loop. */
>> +
>> +__attribute__ ((noinline)) int
>> +foo (int v)
>> +{
>> + int i;
>> + int result = 1;
>> +
>> + ++v;
>> + for (i = 0; i < N; i++)
>> + result *= v;
>> +
>> + return result;
>> +}
>> +
>> +int
>> +main (void)
>> +{
>> + int res;
>> +
>> + check_vect ();
>> +
>> + res = foo (1);
>> + if (res != RES)
>> + abort ();
>> +
>> + return 0;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
>> +/* { dg-final { cleanup-tree-dump "vect" } } */
>> +
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Relax the requirement of reduction pattern in GCC vectorizer.
2013-10-02 18:18 ` Cong Hou
@ 2013-10-15 0:59 ` Cong Hou
0 siblings, 0 replies; 6+ messages in thread
From: Cong Hou @ 2013-10-15 0:59 UTC (permalink / raw)
To: GCC Patches; +Cc: Richard Guenther
Ping...
thanks,
Cong
On Wed, Oct 2, 2013 at 11:18 AM, Cong Hou <congh@google.com> wrote:
> Ping.. Any comment on this patch?
>
>
> thanks,
> Cong
>
>
> On Sat, Sep 28, 2013 at 9:34 AM, Xinliang David Li <davidxl@google.com> wrote:
>> You can also add a test case of this form:
>>
>> int foo( int t, int n, int *dst)
>> {
>> int j = 0;
>> int s = 1;
>> t++;
>> for (j = 0; j < n; j++)
>> {
>> dst[j] = t;
>> s *= t;
>> }
>>
>> return s;
>> }
>>
>> where without the fix the loop vectorization is missed.
>>
>> David
>>
>> On Fri, Sep 27, 2013 at 6:28 PM, Cong Hou <congh@google.com> wrote:
>>> The current GCC vectorizer requires the following pattern as a simple
>>> reduction computation:
>>>
>>> loop_header:
>>> a1 = phi < a0, a2 >
>>> a3 = ...
>>> a2 = operation (a3, a1)
>>>
>>> But a3 can also be defined outside of the loop. For example, the
>>> following loop can benefit from vectorization but the GCC vectorizer
>>> fails to vectorize it:
>>>
>>>
>>> int foo(int v)
>>> {
>>> int s = 1;
>>> ++v;
>>> for (int i = 0; i < 100000; ++i)
>>> s *= v;
>>> return s;
>>> }
>>>
>>>
>>> This patch relaxes the original requirement by also considering the
>>> following pattern:
>>>
>>>
>>> a3 = ...
>>> loop_header:
>>> a1 = phi < a0, a2 >
>>> a2 = operation (a3, a1)
>>>
>>>
>>> A test case is also added. The patch is tested on x86-64.
>>>
>>>
>>> thanks,
>>> Cong
>>>
>>> ================================
>>>
>>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>>> index 39c786e..45c1667 100644
>>> --- a/gcc/ChangeLog
>>> +++ b/gcc/ChangeLog
>>> @@ -1,3 +1,9 @@
>>> +2013-09-27 Cong Hou <congh@google.com>
>>> +
>>> + * tree-vect-loop.c: Relax the requirement of the reduction
>>> + pattern so that one operand of the reduction operation can
>>> + come from outside of the loop.
>>> +
>>> 2013-09-25 Tom Tromey <tromey@redhat.com>
>>>
>>> * Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H)
>>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>>> index 09644d2..90496a2 100644
>>> --- a/gcc/testsuite/ChangeLog
>>> +++ b/gcc/testsuite/ChangeLog
>>> @@ -1,3 +1,7 @@
>>> +2013-09-27 Cong Hou <congh@google.com>
>>> +
>>> + * gcc.dg/vect/vect-reduc-pattern-3.c: New test.
>>> +
>>> 2013-09-25 Marek Polacek <polacek@redhat.com>
>>>
>>> PR sanitizer/58413
>>> diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
>>> index 2871ba1..3c51c3b 100644
>>> --- a/gcc/tree-vect-loop.c
>>> +++ b/gcc/tree-vect-loop.c
>>> @@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info,
>>> gimple phi, gimple first_stmt)
>>> a3 = ...
>>> a2 = operation (a3, a1)
>>>
>>> + or
>>> +
>>> + a3 = ...
>>> + loop_header:
>>> + a1 = phi < a0, a2 >
>>> + a2 = operation (a3, a1)
>>> +
>>> such that:
>>> 1. operation is commutative and associative and it is safe to
>>> change the order of the computation (if CHECK_REDUCTION is true)
>>> @@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info
>>> loop_info, gimple phi,
>>> if (def2 && def2 == phi
>>> && (code == COND_EXPR
>>> || !def1 || gimple_nop_p (def1)
>>> + || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
>>> || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
>>> && (is_gimple_assign (def1)
>>> || is_gimple_call (def1)
>>> @@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info
>>> loop_info, gimple phi,
>>> if (def1 && def1 == phi
>>> && (code == COND_EXPR
>>> || !def2 || gimple_nop_p (def2)
>>> + || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
>>> || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
>>> && (is_gimple_assign (def2)
>>> || is_gimple_call (def2)
>>> diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>>> gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>>> new file mode 100644
>>> index 0000000..06a9416
>>> --- /dev/null
>>> +++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>>> @@ -0,0 +1,41 @@
>>> +/* { dg-require-effective-target vect_int } */
>>> +
>>> +#include <stdarg.h>
>>> +#include "tree-vect.h"
>>> +
>>> +#define N 10
>>> +#define RES 1024
>>> +
>>> +/* A reduction pattern in which there is no data ref in
>>> + the loop and one operand is defined outside of the loop. */
>>> +
>>> +__attribute__ ((noinline)) int
>>> +foo (int v)
>>> +{
>>> + int i;
>>> + int result = 1;
>>> +
>>> + ++v;
>>> + for (i = 0; i < N; i++)
>>> + result *= v;
>>> +
>>> + return result;
>>> +}
>>> +
>>> +int
>>> +main (void)
>>> +{
>>> + int res;
>>> +
>>> + check_vect ();
>>> +
>>> + res = foo (1);
>>> + if (res != RES)
>>> + abort ();
>>> +
>>> + return 0;
>>> +}
>>> +
>>> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
>>> +/* { dg-final { cleanup-tree-dump "vect" } } */
>>> +
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Relax the requirement of reduction pattern in GCC vectorizer.
2013-09-28 7:34 [PATCH] Relax the requirement of reduction pattern in GCC vectorizer Cong Hou
2013-09-28 20:24 ` Xinliang David Li
@ 2013-10-15 13:56 ` Richard Biener
2013-10-15 17:58 ` Cong Hou
1 sibling, 1 reply; 6+ messages in thread
From: Richard Biener @ 2013-10-15 13:56 UTC (permalink / raw)
To: Cong Hou; +Cc: GCC Patches, David Li
On Sat, Sep 28, 2013 at 3:28 AM, Cong Hou <congh@google.com> wrote:
> The current GCC vectorizer requires the following pattern as a simple
> reduction computation:
>
> loop_header:
> a1 = phi < a0, a2 >
> a3 = ...
> a2 = operation (a3, a1)
>
> But a3 can also be defined outside of the loop. For example, the
> following loop can benefit from vectorization but the GCC vectorizer
> fails to vectorize it:
>
>
> int foo(int v)
> {
> int s = 1;
> ++v;
> for (int i = 0; i < 100000; ++i)
> s *= v;
> return s;
> }
>
>
> This patch relaxes the original requirement by also considering the
> following pattern:
>
>
> a3 = ...
> loop_header:
> a1 = phi < a0, a2 >
> a2 = operation (a3, a1)
>
>
> A test case is also added. The patch is tested on x86-64.
>
>
> thanks,
> Cong
>
> ================================
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 39c786e..45c1667 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,9 @@
> +2013-09-27 Cong Hou <congh@google.com>
> +
> + * tree-vect-loop.c: Relax the requirement of the reduction
ChangeLog format is
<tab>* tree-vect-loop.c (vect_is_simple_reduction_1): Relax the
<tab>requirement of the reduction.
Ok with that change.
Thanks,
Richard.
> + pattern so that one operand of the reduction operation can
> + come from outside of the loop.
> +
> 2013-09-25 Tom Tromey <tromey@redhat.com>
>
> * Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H)
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 09644d2..90496a2 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,3 +1,7 @@
> +2013-09-27 Cong Hou <congh@google.com>
> +
> + * gcc.dg/vect/vect-reduc-pattern-3.c: New test.
> +
> 2013-09-25 Marek Polacek <polacek@redhat.com>
>
> PR sanitizer/58413
> diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
> index 2871ba1..3c51c3b 100644
> --- a/gcc/tree-vect-loop.c
> +++ b/gcc/tree-vect-loop.c
> @@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info,
> gimple phi, gimple first_stmt)
> a3 = ...
> a2 = operation (a3, a1)
>
> + or
> +
> + a3 = ...
> + loop_header:
> + a1 = phi < a0, a2 >
> + a2 = operation (a3, a1)
> +
> such that:
> 1. operation is commutative and associative and it is safe to
> change the order of the computation (if CHECK_REDUCTION is true)
> @@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info
> loop_info, gimple phi,
> if (def2 && def2 == phi
> && (code == COND_EXPR
> || !def1 || gimple_nop_p (def1)
> + || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
> || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
> && (is_gimple_assign (def1)
> || is_gimple_call (def1)
> @@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info
> loop_info, gimple phi,
> if (def1 && def1 == phi
> && (code == COND_EXPR
> || !def2 || gimple_nop_p (def2)
> + || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
> || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
> && (is_gimple_assign (def2)
> || is_gimple_call (def2)
> diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
> gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
> new file mode 100644
> index 0000000..06a9416
> --- /dev/null
> +++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
> @@ -0,0 +1,41 @@
> +/* { dg-require-effective-target vect_int } */
> +
> +#include <stdarg.h>
> +#include "tree-vect.h"
> +
> +#define N 10
> +#define RES 1024
> +
> +/* A reduction pattern in which there is no data ref in
> + the loop and one operand is defined outside of the loop. */
> +
> +__attribute__ ((noinline)) int
> +foo (int v)
> +{
> + int i;
> + int result = 1;
> +
> + ++v;
> + for (i = 0; i < N; i++)
> + result *= v;
> +
> + return result;
> +}
> +
> +int
> +main (void)
> +{
> + int res;
> +
> + check_vect ();
> +
> + res = foo (1);
> + if (res != RES)
> + abort ();
> +
> + return 0;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
> +/* { dg-final { cleanup-tree-dump "vect" } } */
> +
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH] Relax the requirement of reduction pattern in GCC vectorizer.
2013-10-15 13:56 ` Richard Biener
@ 2013-10-15 17:58 ` Cong Hou
0 siblings, 0 replies; 6+ messages in thread
From: Cong Hou @ 2013-10-15 17:58 UTC (permalink / raw)
To: Richard Biener; +Cc: GCC Patches, David Li
I have corrected the ChangeLog format, and committed this patch.
Thank you!
Cong
On Tue, Oct 15, 2013 at 6:38 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Sat, Sep 28, 2013 at 3:28 AM, Cong Hou <congh@google.com> wrote:
>> The current GCC vectorizer requires the following pattern as a simple
>> reduction computation:
>>
>> loop_header:
>> a1 = phi < a0, a2 >
>> a3 = ...
>> a2 = operation (a3, a1)
>>
>> But a3 can also be defined outside of the loop. For example, the
>> following loop can benefit from vectorization but the GCC vectorizer
>> fails to vectorize it:
>>
>>
>> int foo(int v)
>> {
>> int s = 1;
>> ++v;
>> for (int i = 0; i < 100000; ++i)
>> s *= v;
>> return s;
>> }
>>
>>
>> This patch relaxes the original requirement by also considering the
>> following pattern:
>>
>>
>> a3 = ...
>> loop_header:
>> a1 = phi < a0, a2 >
>> a2 = operation (a3, a1)
>>
>>
>> A test case is also added. The patch is tested on x86-64.
>>
>>
>> thanks,
>> Cong
>>
>> ================================
>>
>> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
>> index 39c786e..45c1667 100644
>> --- a/gcc/ChangeLog
>> +++ b/gcc/ChangeLog
>> @@ -1,3 +1,9 @@
>> +2013-09-27 Cong Hou <congh@google.com>
>> +
>> + * tree-vect-loop.c: Relax the requirement of the reduction
>
> ChangeLog format is
>
> <tab>* tree-vect-loop.c (vect_is_simple_reduction_1): Relax the
> <tab>requirement of the reduction.
>
> Ok with that change.
>
> Thanks,
> Richard.
>
>> + pattern so that one operand of the reduction operation can
>> + come from outside of the loop.
>> +
>> 2013-09-25 Tom Tromey <tromey@redhat.com>
>>
>> * Makefile.in (PARTITION_H, LTO_SYMTAB_H, COMMON_TARGET_DEF_H)
>> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
>> index 09644d2..90496a2 100644
>> --- a/gcc/testsuite/ChangeLog
>> +++ b/gcc/testsuite/ChangeLog
>> @@ -1,3 +1,7 @@
>> +2013-09-27 Cong Hou <congh@google.com>
>> +
>> + * gcc.dg/vect/vect-reduc-pattern-3.c: New test.
>> +
>> 2013-09-25 Marek Polacek <polacek@redhat.com>
>>
>> PR sanitizer/58413
>> diff --git a/gcc/tree-vect-loop.c b/gcc/tree-vect-loop.c
>> index 2871ba1..3c51c3b 100644
>> --- a/gcc/tree-vect-loop.c
>> +++ b/gcc/tree-vect-loop.c
>> @@ -2091,6 +2091,13 @@ vect_is_slp_reduction (loop_vec_info loop_info,
>> gimple phi, gimple first_stmt)
>> a3 = ...
>> a2 = operation (a3, a1)
>>
>> + or
>> +
>> + a3 = ...
>> + loop_header:
>> + a1 = phi < a0, a2 >
>> + a2 = operation (a3, a1)
>> +
>> such that:
>> 1. operation is commutative and associative and it is safe to
>> change the order of the computation (if CHECK_REDUCTION is true)
>> @@ -2451,6 +2458,7 @@ vect_is_simple_reduction_1 (loop_vec_info
>> loop_info, gimple phi,
>> if (def2 && def2 == phi
>> && (code == COND_EXPR
>> || !def1 || gimple_nop_p (def1)
>> + || !flow_bb_inside_loop_p (loop, gimple_bb (def1))
>> || (def1 && flow_bb_inside_loop_p (loop, gimple_bb (def1))
>> && (is_gimple_assign (def1)
>> || is_gimple_call (def1)
>> @@ -2469,6 +2477,7 @@ vect_is_simple_reduction_1 (loop_vec_info
>> loop_info, gimple phi,
>> if (def1 && def1 == phi
>> && (code == COND_EXPR
>> || !def2 || gimple_nop_p (def2)
>> + || !flow_bb_inside_loop_p (loop, gimple_bb (def2))
>> || (def2 && flow_bb_inside_loop_p (loop, gimple_bb (def2))
>> && (is_gimple_assign (def2)
>> || is_gimple_call (def2)
>> diff --git gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>> gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>> new file mode 100644
>> index 0000000..06a9416
>> --- /dev/null
>> +++ gcc/testsuite/gcc.dg/vect/vect-reduc-pattern-3.c
>> @@ -0,0 +1,41 @@
>> +/* { dg-require-effective-target vect_int } */
>> +
>> +#include <stdarg.h>
>> +#include "tree-vect.h"
>> +
>> +#define N 10
>> +#define RES 1024
>> +
>> +/* A reduction pattern in which there is no data ref in
>> + the loop and one operand is defined outside of the loop. */
>> +
>> +__attribute__ ((noinline)) int
>> +foo (int v)
>> +{
>> + int i;
>> + int result = 1;
>> +
>> + ++v;
>> + for (i = 0; i < N; i++)
>> + result *= v;
>> +
>> + return result;
>> +}
>> +
>> +int
>> +main (void)
>> +{
>> + int res;
>> +
>> + check_vect ();
>> +
>> + res = foo (1);
>> + if (res != RES)
>> + abort ();
>> +
>> + return 0;
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "vectorized 1 loops" 1 "vect" } } */
>> +/* { dg-final { cleanup-tree-dump "vect" } } */
>> +
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2013-10-15 17:19 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2013-09-28 7:34 [PATCH] Relax the requirement of reduction pattern in GCC vectorizer Cong Hou
2013-09-28 20:24 ` Xinliang David Li
2013-10-02 18:18 ` Cong Hou
2013-10-15 0:59 ` Cong Hou
2013-10-15 13:56 ` Richard Biener
2013-10-15 17:58 ` Cong Hou
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).