[PATCH GCC][4/7]Choose exit edge/path when removing inner loop's exit statement

[PATCH GCC][4/7]Choose exit edge/path when removing inner loop's exit statement

[Bin Cheng]

[-- Attachment #1: Type: text/plain, Size: 829 bytes --]

Hi,
Function generate_loops_for_partition chooses arbitrary path when removing exit
condition not in partition.  This is fine for now because it's impossible to have
loop exit condition in case of innermost distribution.  After extending to loop
nest distribution, we must choose exit edge/path for inner loop's exit condition,
otherwise an infinite empty loop will be generated.  Test case added.

Bootstrap and test in patch set on x86_64 and AArch64, is it OK?

Thanks,
bin
2017-10-04  Bin Cheng  <bin.cheng@arm.com>

	* tree-loop-distribution.c (generate_loops_for_partition): Remove
	inner loop's exit stmt by making it always exit the loop, otherwise
	we would generate an infinite empty loop.

gcc/testsuite/ChangeLog
2017-10-04  Bin Cheng  <bin.cheng@arm.com>

	* gcc.dg/tree-ssa/ldist-27.c: New test.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0004-loop_nest-exit-cond-distribution.txt.patch --]
[-- Type: text/x-patch; name="0004-loop_nest-exit-cond-distribution.txt.patch", Size: 2813 bytes --]

From 29f15d5a166b139d8d2dad2ee798c4d0a338f820 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Mon, 25 Sep 2017 16:52:42 +0100
Subject: [PATCH 4/7] loop_nest-exit-cond-distribution.txt

---
 gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c | 38 ++++++++++++++++++++++++++++++++
 gcc/tree-loop-distribution.c             | 16 +++++++++++---
 2 files changed, 51 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
new file mode 100644
index 0000000..3580c65
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
@@ -0,0 +1,38 @@
+/* { dg-do run } */
+/* { dg-options "-O3 -ftree-loop-distribute-patterns -fdump-tree-ldist-details" } */
+
+#define M (300)
+#define N (200)
+
+struct st
+{
+  double a[M];
+  double b[M];
+  double c[M][N];
+};
+
+int __attribute__ ((noinline)) foo (struct st *s)
+{
+  int i, j;
+  for (i = 0; i != M;)
+    {
+      s->a[i] = 0.0;
+      s->b[i] = 1.0;
+      for (j = 0; 1; ++j)
+	{
+	  if (j == N) goto L2;
+	  s->c[i][j] = 0.0;
+	}
+L2:
+      ++i;
+    }
+  return 0;
+}
+
+int main (void)
+{
+  struct st s;
+  return foo (&s);
+}
+
+/* { dg-final { scan-tree-dump "distributed: split to " "ldist" } } */
diff --git a/gcc/tree-loop-distribution.c b/gcc/tree-loop-distribution.c
index 3db3d6e..999b32e 100644
--- a/gcc/tree-loop-distribution.c
+++ b/gcc/tree-loop-distribution.c
@@ -830,6 +830,10 @@ generate_loops_for_partition (struct loop *loop, partition *partition,
   for (i = 0; i < loop->num_nodes; i++)
     {
       basic_block bb = bbs[i];
+      edge inner_exit = NULL;
+
+      if (loop != bb->loop_father)
+	inner_exit = single_exit (bb->loop_father);
 
       for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
 	{
@@ -848,11 +852,17 @@ generate_loops_for_partition (struct loop *loop, partition *partition,
 	      && !is_gimple_debug (stmt)
 	      && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
 	    {
-	      /* Choose an arbitrary path through the empty CFG part
-		 that this unnecessary control stmt controls.  */
+	      /* In distribution of loop nest, if bb is inner loop's exit_bb,
+		 we choose its exit edge/path in order to avoid generating
+		 infinite loop.  For all other cases, we choose an arbitrary
+		 path through the empty CFG part that this unnecessary
+		 control stmt controls.  */
 	      if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
 		{
-		  gimple_cond_make_false (cond_stmt);
+		  if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
+		    gimple_cond_make_true (cond_stmt);
+		  else
+		    gimple_cond_make_false (cond_stmt);
 		  update_stmt (stmt);
 		}
 	      else if (gimple_code (stmt) == GIMPLE_SWITCH)
-- 
1.9.1

Re: [PATCH GCC][4/7]Choose exit edge/path when removing inner loop's exit statement

[Richard Biener]

On Thu, Oct 5, 2017 at 3:16 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
> Hi,
> Function generate_loops_for_partition chooses arbitrary path when removing exit
> condition not in partition.  This is fine for now because it's impossible to have
> loop exit condition in case of innermost distribution.  After extending to loop
> nest distribution, we must choose exit edge/path for inner loop's exit condition,
> otherwise an infinite empty loop will be generated.  Test case added.
>
> Bootstrap and test in patch set on x86_64 and AArch64, is it OK?

Ok.

Richard.

> Thanks,
> bin
> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>
>         * tree-loop-distribution.c (generate_loops_for_partition): Remove
>         inner loop's exit stmt by making it always exit the loop, otherwise
>         we would generate an infinite empty loop.
>
> gcc/testsuite/ChangeLog
> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>
>         * gcc.dg/tree-ssa/ldist-27.c: New test.

Re: [PATCH GCC][4/7]Choose exit edge/path when removing inner loop's exit statement

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1255 bytes --]

On 10/09/2017 03:34 PM, Richard Biener wrote:
> On Thu, Oct 5, 2017 at 3:16 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>> Hi,
>> Function generate_loops_for_partition chooses arbitrary path when removing exit
>> condition not in partition.  This is fine for now because it's impossible to have
>> loop exit condition in case of innermost distribution.  After extending to loop
>> nest distribution, we must choose exit edge/path for inner loop's exit condition,
>> otherwise an infinite empty loop will be generated.  Test case added.
>>
>> Bootstrap and test in patch set on x86_64 and AArch64, is it OK?
> 
> Ok.
> 
> Richard.
> 
>> Thanks,
>> bin
>> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>>
>>          * tree-loop-distribution.c (generate_loops_for_partition): Remove
>>          inner loop's exit stmt by making it always exit the loop, otherwise
>>          we would generate an infinite empty loop.
>>
>> gcc/testsuite/ChangeLog
>> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>>
>>          * gcc.dg/tree-ssa/ldist-27.c: New test.

Hi,

I've committed patch below to specify the stack size requirements of 
this test-case (fixing the test failure for nvptx).

Does it make sense to trim down the test-case using #ifdef STACK_SIZE?

Thanks,
- Tom

[-- Attachment #2: 0001-Specify-required-stack-size-for-gcc.dg-tree-ssa-ldist-27.c.patch --]
[-- Type: text/x-patch, Size: 697 bytes --]

Specify required stack size for gcc.dg/tree-ssa/ldist-27.c

2017-10-19  Tom de Vries  <tom@codesourcery.com>

	* gcc.dg/tree-ssa/ldist-27.c: Use dg-require-stack-size.

---
 gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
index 3580c65..cd9696e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
@@ -1,5 +1,6 @@
 /* { dg-do run } */
 /* { dg-options "-O3 -ftree-loop-distribute-patterns -fdump-tree-ldist-details" } */
+/* { dg-require-stack-size "(300 + 200 + 300 * 200) * 8" } */
 
 #define M (300)
 #define N (200)

Re: [PATCH GCC][4/7]Choose exit edge/path when removing inner loop's exit statement

[Bin.Cheng]

On Thu, Oct 19, 2017 at 9:31 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> On 10/09/2017 03:34 PM, Richard Biener wrote:
>>
>> On Thu, Oct 5, 2017 at 3:16 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>
>>> Hi,
>>> Function generate_loops_for_partition chooses arbitrary path when
>>> removing exit
>>> condition not in partition.  This is fine for now because it's impossible
>>> to have
>>> loop exit condition in case of innermost distribution.  After extending
>>> to loop
>>> nest distribution, we must choose exit edge/path for inner loop's exit
>>> condition,
>>> otherwise an infinite empty loop will be generated.  Test case added.
>>>
>>> Bootstrap and test in patch set on x86_64 and AArch64, is it OK?
>>
>>
>> Ok.
>>
>> Richard.
>>
>>> Thanks,
>>> bin
>>> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>>>
>>>          * tree-loop-distribution.c (generate_loops_for_partition):
>>> Remove
>>>          inner loop's exit stmt by making it always exit the loop,
>>> otherwise
>>>          we would generate an infinite empty loop.
>>>
>>> gcc/testsuite/ChangeLog
>>> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>>>
>>>          * gcc.dg/tree-ssa/ldist-27.c: New test.
>
>
> Hi,
>
> I've committed patch below to specify the stack size requirements of this
> test-case (fixing the test failure for nvptx).
Hi,
Maybe we can simply make the structure a global variable?

Thanks,
bin
>
> Does it make sense to trim down the test-case using #ifdef STACK_SIZE?
>
> Thanks,
> - Tom

Re: [PATCH GCC][4/7]Choose exit edge/path when removing inner loop's exit statement

[Tom de Vries]

[-- Attachment #1: Type: text/plain, Size: 1526 bytes --]

On 10/19/2017 10:49 AM, Bin.Cheng wrote:
> On Thu, Oct 19, 2017 at 9:31 AM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> On 10/09/2017 03:34 PM, Richard Biener wrote:
>>>
>>> On Thu, Oct 5, 2017 at 3:16 PM, Bin Cheng <Bin.Cheng@arm.com> wrote:
>>>>
>>>> Hi,
>>>> Function generate_loops_for_partition chooses arbitrary path when
>>>> removing exit
>>>> condition not in partition.  This is fine for now because it's impossible
>>>> to have
>>>> loop exit condition in case of innermost distribution.  After extending
>>>> to loop
>>>> nest distribution, we must choose exit edge/path for inner loop's exit
>>>> condition,
>>>> otherwise an infinite empty loop will be generated.  Test case added.
>>>>
>>>> Bootstrap and test in patch set on x86_64 and AArch64, is it OK?
>>>
>>>
>>> Ok.
>>>
>>> Richard.
>>>
>>>> Thanks,
>>>> bin
>>>> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>           * tree-loop-distribution.c (generate_loops_for_partition):
>>>> Remove
>>>>           inner loop's exit stmt by making it always exit the loop,
>>>> otherwise
>>>>           we would generate an infinite empty loop.
>>>>
>>>> gcc/testsuite/ChangeLog
>>>> 2017-10-04  Bin Cheng  <bin.cheng@arm.com>
>>>>
>>>>           * gcc.dg/tree-ssa/ldist-27.c: New test.
>>
>>
>> Hi,
>>
>> I've committed patch below to specify the stack size requirements of this
>> test-case (fixing the test failure for nvptx).
> Hi,
> Maybe we can simply make the structure a global variable?
> 

Works for me.

Committed as attached.

Thanks,
- Tom

[-- Attachment #2: 0001-Reduce-stack-size-in-gcc.dg-tree-ssa-ldist-27.c.patch --]
[-- Type: text/x-patch, Size: 1084 bytes --]

Reduce stack size in gcc.dg/tree-ssa/ldist-27.c

2017-10-20  Tom de Vries  <tom@codesourcery.com>

	* gcc.dg/tree-ssa/ldist-27.c: Remove dg-require-stack-size.
	(main): Move s ...
	(s): ... here.

---
 gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c b/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
index cd9696e..b1fd024 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ldist-27.c
@@ -1,6 +1,5 @@
 /* { dg-do run } */
 /* { dg-options "-O3 -ftree-loop-distribute-patterns -fdump-tree-ldist-details" } */
-/* { dg-require-stack-size "(300 + 200 + 300 * 200) * 8" } */
 
 #define M (300)
 #define N (200)
@@ -12,7 +11,8 @@ struct st
   double c[M][N];
 };
 
-int __attribute__ ((noinline)) foo (struct st *s)
+int __attribute__ ((noinline))
+foo (struct st *s)
 {
   int i, j;
   for (i = 0; i != M;)
@@ -30,9 +30,11 @@ L2:
   return 0;
 }
 
-int main (void)
+struct st s;
+
+int
+main (void)
 {
-  struct st s;
   return foo (&s);
 }