[PATCH] Discard Scops for which entry==exit

[PATCH] Discard Scops for which entry==exit

[Aditya Kumar]

In this patch we discard the scops where entry and exit are the same BB.
This is an effort to remove graphite-scop-detection.c:limit_scops.
Removing the limit_scops function introduces correctness regressions.
We are making relevant changes in incremental steps to fix those bugs,
and finally we intend to remove limit_scops.

2015-06-29  Aditya Kumar  <aditya.k7@samsung.com>
	    Sebastian Pop <s.pop@samsung.com>

        * graphite-scop-detection.c (build_scops_1): Discard scops for which entry==exit


---
 gcc/graphite-scop-detection.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index e8ddecd..f57cc4a 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -810,7 +810,14 @@ build_scops_1 (basic_block current, loop_p outermost_loop,
     {
       open_scop.exit = sinfo.exit;
       gcc_assert (open_scop.exit);
-      scops->safe_push (open_scop);
+      if (open_scop.entry != open_scop.exit)
+	scops->safe_push (open_scop);
+      else
+	{
+	  sinfo.difficult = true;
+	  sinfo.exits = false;
+	  sinfo.exit = NULL;
+	}
     }
 
   result.exit = sinfo.exit;
-- 
2.1.0.243.g30d45f7

Re: [PATCH] Discard Scops for which entry==exit

[Sebastian Pop]

On Mon, Jun 29, 2015 at 3:04 PM, Aditya Kumar <hiraditya@msn.com> wrote:
> In this patch we discard the scops where entry and exit are the same BB.
> This is an effort to remove graphite-scop-detection.c:limit_scops.
> Removing the limit_scops function introduces correctness regressions.
> We are making relevant changes in incremental steps to fix those bugs,
> and finally we intend to remove limit_scops.
>
> 2015-06-29  Aditya Kumar  <aditya.k7@samsung.com>
>             Sebastian Pop <s.pop@samsung.com>
>
>         * graphite-scop-detection.c (build_scops_1): Discard scops for which entry==exit

Looks good to me.
Let's wait on comments from Tobi before pushing this patch.

Thanks,
Sebastian

>
>
> ---
>  gcc/graphite-scop-detection.c | 9 ++++++++-
>  1 file changed, 8 insertions(+), 1 deletion(-)
>
> diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
> index e8ddecd..f57cc4a 100644
> --- a/gcc/graphite-scop-detection.c
> +++ b/gcc/graphite-scop-detection.c
> @@ -810,7 +810,14 @@ build_scops_1 (basic_block current, loop_p outermost_loop,
>      {
>        open_scop.exit = sinfo.exit;
>        gcc_assert (open_scop.exit);
> -      scops->safe_push (open_scop);
> +      if (open_scop.entry != open_scop.exit)
> +       scops->safe_push (open_scop);
> +      else
> +       {
> +         sinfo.difficult = true;
> +         sinfo.exits = false;
> +         sinfo.exit = NULL;
> +       }
>      }
>
>    result.exit = sinfo.exit;
> --
> 2.1.0.243.g30d45f7
>

Re: [PATCH] Discard Scops for which entry==exit

[Tobias Grosser]

On 06/30/2015 02:09 AM, Sebastian Pop wrote:
> On Mon, Jun 29, 2015 at 3:04 PM, Aditya Kumar <hiraditya@msn.com> wrote:
>> In this patch we discard the scops where entry and exit are the same BB.
>> This is an effort to remove graphite-scop-detection.c:limit_scops.
>> Removing the limit_scops function introduces correctness regressions.
>> We are making relevant changes in incremental steps to fix those bugs,
>> and finally we intend to remove limit_scops.
>>
>> 2015-06-29  Aditya Kumar  <aditya.k7@samsung.com>
>>              Sebastian Pop <s.pop@samsung.com>
>>
>>          * graphite-scop-detection.c (build_scops_1): Discard scops for which entry==exit
>
> Looks good to me.
> Let's wait on comments from Tobi before pushing this patch.

Hi Sebastian,

the commit message should probably give a short reasoning why scops with 
entry == exit need to be discarded. I currently don't see why they would 
be incorrect/problematic (despite being possibly very small/empty).

Tobias

Re: [PATCH] Discard Scops for which entry==exit

[Richard Biener]

On Tue, Jun 30, 2015 at 8:11 AM, Tobias Grosser <tobias@grosser.es> wrote:
> On 06/30/2015 02:09 AM, Sebastian Pop wrote:
>>
>> On Mon, Jun 29, 2015 at 3:04 PM, Aditya Kumar <hiraditya@msn.com> wrote:
>>>
>>> In this patch we discard the scops where entry and exit are the same BB.
>>> This is an effort to remove graphite-scop-detection.c:limit_scops.
>>> Removing the limit_scops function introduces correctness regressions.
>>> We are making relevant changes in incremental steps to fix those bugs,
>>> and finally we intend to remove limit_scops.
>>>
>>> 2015-06-29  Aditya Kumar  <aditya.k7@samsung.com>
>>>              Sebastian Pop <s.pop@samsung.com>
>>>
>>>          * graphite-scop-detection.c (build_scops_1): Discard scops for
>>> which entry==exit
>>
>>
>> Looks good to me.
>> Let's wait on comments from Tobi before pushing this patch.
>
>
> Hi Sebastian,
>
> the commit message should probably give a short reasoning why scops with
> entry == exit need to be discarded. I currently don't see why they would be
> incorrect/problematic (despite being possibly very small/empty).

Dependent on how GRAPHITE initializes loops even a loop can consist of a single
basic-block (without LOOPS_HAVE_SIMPLE_LATCHES where you always have at
least two BBs for a loop).

I suppose GRAPHITE does nothing for non-loops and this is what the check is
about?  (so rather require a backedge in the SCOP?)

Of ocurse I also don't see "correctness" issues here, just maybe a waste of
compile-time?

Richard.

> Tobias

RE: [PATCH] Discard Scops for which entry==exit

[Aditya K]

Hi Tobias,
A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed `graphite-scop-detection.c:limit_scops'.
The test case is a scop where entry==exit,

BB5 (*#) -> BB6 (#);
BB6 -> BB5;

In this case BB2 is out of the scop. This is basically an empty (infinite) loop with no entry.

--

(gdb) p debug_loops(3)
loop_0 (header = 0, latch = 1, niter = )
{
  bb_2 (preds = {bb_0 }, succs = {bb_8 bb_3 })
  {
    <bb 2>:
    # VUSE <.MEM_7(D)>
    _5 = *x_10(D)[3];
    if (_5 < 0.0)
      goto <bb 8>;
    else
      goto <bb 3>;

  }
  bb_3 (preds = {bb_2 }, succs = {bb_4 bb_7 })
  {
    <bb 3>:
    if (_5>= 0.0)
      goto <bb 4>;
    else
      goto <bb 7>;

  }
  bb_4 (preds = {bb_3 bb_8 }, succs = {bb_9 })
  {
    <bb 4>:
    # .MEM_19 = PHI <.MEM_7(D)(3), .MEM_14(8)>

  }
  bb_9 (preds = {bb_4 }, succs = {bb_5 })
  {
    <bb 9>:

  }
  bb_7 (preds = {bb_3 }, succs = {bb_1 })
  {
    <bb 7>:
    # VUSE <.MEM_7(D)>
    return;

  }
  bb_8 (preds = {bb_2 }, succs = {bb_4 })
  {
    <bb 8>:
    # .MEM_14 = VDEF <.MEM_7(D)>
    *x_10(D)[3] = 0.0;
    goto <bb 4>;

  }
  loop_2 (header = 5, latch = 6, niter = scev_not_known)
  {
    bb_5 (preds = {bb_9 bb_6 }, succs = {bb_6 })
    {
      <bb 5>:
      # .MEM_25 = PHI <.MEM_19(9), .MEM_25(6)>

    }
    bb_6 (preds = {bb_5 }, succs = {bb_5 })
    {
      <bb 6>:
      goto <bb 5>;

    }
  }
}



digraph all {
0 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 0 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
2 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 2 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
3 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 3 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
4 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 4 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
9 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 9 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
5 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#e41a1c"> 5*# </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
6 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#e41a1c"> 6 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
7 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 7 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
8 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 8 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
1 [label=<
  <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0">
    <TR><TD WIDTH="50" BGCOLOR="#ffffff"> 1 </TD></TR>
  </TABLE>>, shape=box, style="setlinewidth(0)"]
0 -> 2;
2 -> 8;
2 -> 3;
3 -> 4;
3 -> 7;
4 -> 9;
9 -> 5;
5 -> 6;
6 -> 5;
7 -> 1;
8 -> 4;
}


-Aditya

----------------------------------------
> Date: Tue, 30 Jun 2015 08:11:01 +0200
> From: tobias@grosser.es
> To: sebpop@gmail.com; hiraditya@msn.com
> CC: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] Discard Scops for which entry==exit
>
> On 06/30/2015 02:09 AM, Sebastian Pop wrote:
>> On Mon, Jun 29, 2015 at 3:04 PM, Aditya Kumar <hiraditya@msn.com> wrote:
>>> In this patch we discard the scops where entry and exit are the same BB.
>>> This is an effort to remove graphite-scop-detection.c:limit_scops.
>>> Removing the limit_scops function introduces correctness regressions.
>>> We are making relevant changes in incremental steps to fix those bugs,
>>> and finally we intend to remove limit_scops.
>>>
>>> 2015-06-29 Aditya Kumar <aditya.k7@samsung.com>
>>> Sebastian Pop <s.pop@samsung.com>
>>>
>>> * graphite-scop-detection.c (build_scops_1): Discard scops for which entry==exit
>>
>> Looks good to me.
>> Let's wait on comments from Tobi before pushing this patch.
>
> Hi Sebastian,
>
> the commit message should probably give a short reasoning why scops with
> entry == exit need to be discarded. I currently don't see why they would
> be incorrect/problematic (despite being possibly very small/empty).
>
> Tobias
 		 	   		  

Re: [PATCH] Discard Scops for which entry==exit

[Tobias Grosser]

On 06/30/2015 05:47 PM, Aditya K wrote:
> Hi Tobias,
> A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed `graphite-scop-detection.c:limit_scops'.
> The test case is a scop where entry==exit,
>
> BB5 (*#) -> BB6 (#);
> BB6 -> BB5;
>
> In this case BB2 is out of the scop. This is basically an empty (infinite) loop with no entr

OK, maybe mention this in the commit message.


Best,
Tobias

RE: [PATCH] Discard Scops for which entry==exit

[Aditya K]

A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed `graphite-scop-detection.c:limit_scops'.
The test case is a scop where entry==exit,

BB5 (*#) -> BB6 (#);
BB6 -> BB5;

In this case BB2 is out of the scop. This is basically an empty (infinite) loop.



2015-06-29  Aditya Kumar  <aditya.k7@samsung.com>
        Sebastian Pop <s.pop@samsung.com>

        * graphite-scop-detection.c (build_scops_1): Discard scops for which entry==exit


---
 gcc/graphite-scop-detection.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/gcc/graphite-scop-detection.c b/gcc/graphite-scop-detection.c
index e8ddecd..f57cc4a 100644
--- a/gcc/graphite-scop-detection.c
+++ b/gcc/graphite-scop-detection.c
@@ -810,7 +810,14 @@ build_scops_1 (basic_block current, loop_p outermost_loop,
     {
       open_scop.exit = sinfo.exit;
       gcc_assert (open_scop.exit);
-      scops->safe_push (open_scop);
+      if (open_scop.entry != open_scop.exit)
+    scops->safe_push (open_scop);
+      else
+    {
+      sinfo.difficult = true;
+      sinfo.exits = false;
+      sinfo.exit = NULL;
+    }
     }
 
   result.exit = sinfo.exit;
-- 
2.1.0.243.g30d45f7



----------------------------------------
> Date: Thu, 2 Jul 2015 09:53:25 +0200
> From: tobias@grosser.es
> To: hiraditya@msn.com; sebpop@gmail.com
> CC: gcc-patches@gcc.gnu.org
> Subject: Re: [PATCH] Discard Scops for which entry==exit
>
> On 06/30/2015 05:47 PM, Aditya K wrote:
>> Hi Tobias,
>> A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed `graphite-scop-detection.c:limit_scops'.
>> The test case is a scop where entry==exit,
>>
>> BB5 (*#) -> BB6 (#);
>> BB6 -> BB5;
>>
>> In this case BB2 is out of the scop. This is basically an empty (infinite) loop with no entr
>
> OK, maybe mention this in the commit message.
>
>
> Best,
> Tobias
>
 		 	   		  

Re: [PATCH] Discard Scops for which entry==exit

[Tobias Grosser]

On 07/02/2015 05:37 PM, Aditya K wrote:
> A test case (gcc/testsuite/gcc.dg/graphite/pr18792.c) came up when we removed `graphite-scop-detection.c:limit_scops'.
> The test case is a scop where entry==exit,
>
> BB5 (*#) -> BB6 (#);
> BB6 -> BB5;
>
> In this case BB2 is out of the scop. This is basically an empty (infinite) loop.

LGTM.

Tobias