PATCH] tree-ssa-sink: Add heuristics for code sinking

  Hello All:

This patch add heuristics for code sinking opportunities.
Bootstrapped and regtested for powerpc64-linux-gnu.

Thanks & Regards
Ajit

	tree-ssa-sink: Add heuristics for code sinking.

	Add following code sinking heuristics:

	1. from code block dominates the call.
	2. To Code block have uses inside the function call.
	3. Loop headers.
	4. Sinking from code block after call increases register
	pressure.
	5. Sinking calls.

	2023-04-14  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>

gcc/ChangeLog:

	* tree-ssa-sink.cc (statement_sink_location): Add heuristics
	for code sinking.
---
 gcc/tree-ssa-sink.cc | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)
  

On Fri, Apr 14, 2023 at 10:42 AM Ajit Agarwal via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> Hello All:
>
> This patch add heuristics for code sinking opportunities.
> Bootstrapped and regtested for powerpc64-linux-gnu.
>
> Thanks & Regards
> Ajit
>
>         tree-ssa-sink: Add heuristics for code sinking.
>
>         Add following code sinking heuristics:
>
>         1. from code block dominates the call.
>         2. To Code block have uses inside the function call.
>         3. Loop headers.
>         4. Sinking from code block after call increases register
>         pressure.
>         5. Sinking calls.
>
>         2023-04-14  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>
>
> gcc/ChangeLog:
>
>         * tree-ssa-sink.cc (statement_sink_location): Add heuristics
>         for code sinking.
> ---
>  gcc/tree-ssa-sink.cc | 33 +++++++++++++++++++++++++++++++++
>  1 file changed, 33 insertions(+)
>
> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
> index 87b1d40c174..8de88b259a3 100644
> --- a/gcc/tree-ssa-sink.cc
> +++ b/gcc/tree-ssa-sink.cc
> @@ -465,6 +465,39 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>           if (sinkbb == frombb)
>             return false;
>
> +         auto_vec<basic_block> h;
> +         h = get_all_dominated_blocks (CDI_DOMINATORS,
> +                                       frombb);
> +         bool is_call = false;
> +         while (h.length ())
> +           {
> +             basic_block bb = h.pop ();
> +
> +             if (bb == frombb)
> +               continue;
> +
> +             for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
> +               {
> +                 gimple *stmt = gsi_stmt (gsi);
> +
> +                 if (is_gimple_call (stmt))
> +                   {
> +                     is_call = true;
> +                     break;
> +                   }
> +
> +                  if (!gsi_end_p (gsi))
> +                    gsi_prev (&gsi);
> +               }
> +            }
> +
> +           if (!is_gimple_call (stmt)
> +               && (gimple_bb (use) != frombb)
> +               && !is_gimple_call (use)
> +               && dominated_by_p (CDI_DOMINATORS, sinkbb, frombb)
> +               && is_call)
> +              return false;
> +

Sorry, but this lacks a comment, it doesn't explain why the existing heuristics
are not enough (select_best_block), it repeats dominance computing.

More so it lacks a testcase demonstrating the effect.

Richard.

>           if (sinkbb == gimple_bb (use))
>             *togsi = gsi_for_stmt (use);
>           else
> --
> 2.31.1
>
  

Hello Richard:

On 14/04/23 2:29 pm, Richard Biener wrote:
> On Fri, Apr 14, 2023 at 10:42 AM Ajit Agarwal via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>> Hello All:
>>
>> This patch add heuristics for code sinking opportunities.
>> Bootstrapped and regtested for powerpc64-linux-gnu.
>>
>> Thanks & Regards
>> Ajit
>>
>>         tree-ssa-sink: Add heuristics for code sinking.
>>
>>         Add following code sinking heuristics:
>>
>>         1. from code block dominates the call.
>>         2. To Code block have uses inside the function call.
>>         3. Loop headers.
>>         4. Sinking from code block after call increases register
>>         pressure.
>>         5. Sinking calls.
>>
>>         2023-04-14  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>
>>
>> gcc/ChangeLog:
>>
>>         * tree-ssa-sink.cc (statement_sink_location): Add heuristics
>>         for code sinking.
>> ---
>>  gcc/tree-ssa-sink.cc | 33 +++++++++++++++++++++++++++++++++
>>  1 file changed, 33 insertions(+)
>>
>> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
>> index 87b1d40c174..8de88b259a3 100644
>> --- a/gcc/tree-ssa-sink.cc
>> +++ b/gcc/tree-ssa-sink.cc
>> @@ -465,6 +465,39 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>>           if (sinkbb == frombb)
>>             return false;
>>
>> +         auto_vec<basic_block> h;
>> +         h = get_all_dominated_blocks (CDI_DOMINATORS,
>> +                                       frombb);
>> +         bool is_call = false;
>> +         while (h.length ())
>> +           {
>> +             basic_block bb = h.pop ();
>> +
>> +             if (bb == frombb)
>> +               continue;
>> +
>> +             for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
>> +               {
>> +                 gimple *stmt = gsi_stmt (gsi);
>> +
>> +                 if (is_gimple_call (stmt))
>> +                   {
>> +                     is_call = true;
>> +                     break;
>> +                   }
>> +
>> +                  if (!gsi_end_p (gsi))
>> +                    gsi_prev (&gsi);
>> +               }
>> +            }
>> +
>> +           if (!is_gimple_call (stmt)
>> +               && (gimple_bb (use) != frombb)
>> +               && !is_gimple_call (use)
>> +               && dominated_by_p (CDI_DOMINATORS, sinkbb, frombb)
>> +               && is_call)
>> +              return false;
>> +
> 
> Sorry, but this lacks a comment, it doesn't explain why the existing heuristics
> are not enough (select_best_block), it repeats dominance computing.
> 
> More so it lacks a testcase demonstrating the effect.
> 

Added testscases and comments in the code.
The heuristics are added to relieve from register pressure.

Thanks & Regards
Ajit

Here is the patch.

	tree-ssa-sink: Add heuristics for code sinking.

	Add following code sinking heuristics:

	1. from code block dominates the call.
	2. To Code block have uses inside the function call.
	3. Loop headers.
	4. Sinking from code block after call increases register
	pressure.
	5. Sinking calls.

	2023-04-14  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>

gcc/ChangeLog:

	* tree-ssa-sink.cc (statement_sink_location): Add heuristics
	for code sinking.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/ssa-sink-20.c: New testcase.
	* gcc.dg/tree-ssa/ssa-sink-21.c: New testcase.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 ++++++++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 20 ++++++++++++++++++++
 gcc/tree-ssa-sink.cc                        |  6 ++++++
 3 files changed, 42 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
new file mode 100644
index 00000000000..ed2aefc01aa
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink -fdump-tree-optimized" } */
+
+void bar();
+int j;
+void foo(int a, int b, int c, int d, int e, int f)
+{
+  int l;
+  l = a + b + c + d +e + f;
+  if (a != 5)
+    {
+      bar();
+      j = l;
+    }
+}
+/* { dg-final { scan-tree-dump-times "Sunk statements: 1" 0 "sink1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
new file mode 100644
index 00000000000..a39724df8ec
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
@@ -0,0 +1,20 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -fdump-tree-sink-stats" } */
+
+void bar();
+int j, x;
+void foo(int a, int b, int c, int d, int e, int f)
+{
+  int l;
+  l = a + b + c + d +e + f;
+  if (a != 5)
+    {
+      bar();
+      if (b != 3)
+        x = 3;
+      else
+        x = 5;
+      j = l;
+    }
+}
+/* { dg-final { scan-tree-dump-times "Sunk statements: 1" 0 "sink1" } } */
diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
index 8de88b259a3..932fd71bec2 100644
--- a/gcc/tree-ssa-sink.cc
+++ b/gcc/tree-ssa-sink.cc
@@ -465,6 +465,12 @@ statement_sink_location (gimple *stmt, basic_block frombb,
 	  if (sinkbb == frombb)
 	    return false;
 
+	  /* The below heuristics describes the following.
+	     a) If the candidate to sink has call in the dominator basic
+	     basic blocks.
+	     b) statement to sink doesn't have  use in the call.
+	     c) candidate block  dominates sink block.
+	     In the above cases are true then don't do code sinking.  */
 	  auto_vec<basic_block> h;
 	  h = get_all_dominated_blocks (CDI_DOMINATORS,
 					frombb);
  

On Fri, Apr 14, 2023 at 12:08 PM Ajit Agarwal <aagarwa1@linux.ibm.com> wrote:
>
> Hello Richard:
>
> On 14/04/23 2:29 pm, Richard Biener wrote:
> > On Fri, Apr 14, 2023 at 10:42 AM Ajit Agarwal via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >>
> >> Hello All:
> >>
> >> This patch add heuristics for code sinking opportunities.
> >> Bootstrapped and regtested for powerpc64-linux-gnu.
> >>
> >> Thanks & Regards
> >> Ajit
> >>
> >>         tree-ssa-sink: Add heuristics for code sinking.
> >>
> >>         Add following code sinking heuristics:
> >>
> >>         1. from code block dominates the call.
> >>         2. To Code block have uses inside the function call.
> >>         3. Loop headers.
> >>         4. Sinking from code block after call increases register
> >>         pressure.
> >>         5. Sinking calls.
> >>
> >>         2023-04-14  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>
> >>
> >> gcc/ChangeLog:
> >>
> >>         * tree-ssa-sink.cc (statement_sink_location): Add heuristics
> >>         for code sinking.
> >> ---
> >>  gcc/tree-ssa-sink.cc | 33 +++++++++++++++++++++++++++++++++
> >>  1 file changed, 33 insertions(+)
> >>
> >> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
> >> index 87b1d40c174..8de88b259a3 100644
> >> --- a/gcc/tree-ssa-sink.cc
> >> +++ b/gcc/tree-ssa-sink.cc
> >> @@ -465,6 +465,39 @@ statement_sink_location (gimple *stmt, basic_block frombb,
> >>           if (sinkbb == frombb)
> >>             return false;
> >>
> >> +         auto_vec<basic_block> h;
> >> +         h = get_all_dominated_blocks (CDI_DOMINATORS,
> >> +                                       frombb);
> >> +         bool is_call = false;
> >> +         while (h.length ())
> >> +           {
> >> +             basic_block bb = h.pop ();
> >> +
> >> +             if (bb == frombb)
> >> +               continue;
> >> +
> >> +             for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
> >> +               {
> >> +                 gimple *stmt = gsi_stmt (gsi);
> >> +
> >> +                 if (is_gimple_call (stmt))
> >> +                   {
> >> +                     is_call = true;
> >> +                     break;
> >> +                   }
> >> +
> >> +                  if (!gsi_end_p (gsi))
> >> +                    gsi_prev (&gsi);
> >> +               }
> >> +            }
> >> +
> >> +           if (!is_gimple_call (stmt)
> >> +               && (gimple_bb (use) != frombb)
> >> +               && !is_gimple_call (use)
> >> +               && dominated_by_p (CDI_DOMINATORS, sinkbb, frombb)
> >> +               && is_call)
> >> +              return false;
> >> +
> >
> > Sorry, but this lacks a comment, it doesn't explain why the existing heuristics
> > are not enough (select_best_block), it repeats dominance computing.
> >
> > More so it lacks a testcase demonstrating the effect.
> >
>
> Added testscases and comments in the code.
> The heuristics are added to relieve from register pressure.
>
> Thanks & Regards
> Ajit
>
> Here is the patch.
>
>         tree-ssa-sink: Add heuristics for code sinking.
>
>         Add following code sinking heuristics:
>
>         1. from code block dominates the call.
>         2. To Code block have uses inside the function call.
>         3. Loop headers.
>         4. Sinking from code block after call increases register
>         pressure.
>         5. Sinking calls.
>
>         2023-04-14  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>
>
> gcc/ChangeLog:
>
>         * tree-ssa-sink.cc (statement_sink_location): Add heuristics
>         for code sinking.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/ssa-sink-20.c: New testcase.
>         * gcc.dg/tree-ssa/ssa-sink-21.c: New testcase.
> ---
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c | 16 ++++++++++++++++
>  gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 20 ++++++++++++++++++++
>  gcc/tree-ssa-sink.cc                        |  6 ++++++
>  3 files changed, 42 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
> new file mode 100644
> index 00000000000..ed2aefc01aa
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
> @@ -0,0 +1,16 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-sink -fdump-tree-optimized" } */
> +
> +void bar();
> +int j;
> +void foo(int a, int b, int c, int d, int e, int f)
> +{
> +  int l;
> +  l = a + b + c + d +e + f;
> +  if (a != 5)
> +    {

why should we not sink the computes inside if (a != 5)?

> +      bar();

you probably want to avoid sinking after the call but since this is
all in a single BB, GIMPLE doesn't really define a schedule of
stmts here and so passes like sinking shouldn't really bother to
look.

> +      j = l;
> +    }
> +}
> +/* { dg-final { scan-tree-dump-times "Sunk statements: 1" 0 "sink1" } } */

Btw, you probably want to check "Sunk statements: 0" 1 "sink1" instead.
Otherwise sinking two stmts would be OK?

> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> new file mode 100644
> index 00000000000..a39724df8ec
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
> @@ -0,0 +1,20 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-sink-stats" } */
> +
> +void bar();
> +int j, x;
> +void foo(int a, int b, int c, int d, int e, int f)
> +{
> +  int l;
> +  l = a + b + c + d +e + f;
> +  if (a != 5)
> +    {

same here

> +      bar();
> +      if (b != 3)
> +        x = 3;
> +      else
> +        x = 5;
> +      j = l;
> +    }
> +}
> +/* { dg-final { scan-tree-dump-times "Sunk statements: 1" 0 "sink1" } } */
> diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
> index 8de88b259a3..932fd71bec2 100644
> --- a/gcc/tree-ssa-sink.cc
> +++ b/gcc/tree-ssa-sink.cc
> @@ -465,6 +465,12 @@ statement_sink_location (gimple *stmt, basic_block frombb,
>           if (sinkbb == frombb)
>             return false;
>
> +         /* The below heuristics describes the following.
> +            a) If the candidate to sink has call in the dominator basic
> +            basic blocks.
> +            b) statement to sink doesn't have  use in the call.
> +            c) candidate block  dominates sink block.
> +            In the above cases are true then don't do code sinking.  */

but then the existing heuristic would try to find a better block.  Consider

+void bar();
+int j, x;
+void foo(int a, int b, int c, int d, int e, int f)
+{
+  int l;
+  l = a + b + c + d +e + f;
+  if (a != 5)
+    {
+      if (b != 3)
+        x = 3;
+      else
+        x = 5;
+      bar();
+      j = l;
+    }
+}

we do not want to completely disable sinking but might want to sink
before bar() instead of not at all if the position after bar() we'd otherwise
sink to is executed with the same conditions than the position before bar ().

So I don't think the implementation is good at all - it wires things in the
wrong place.

Richard.

>           auto_vec<basic_block> h;
>           h = get_all_dominated_blocks (CDI_DOMINATORS,
>                                         frombb);
> --
> 2.31.1
>
>
> > Richard.
> >
> >>           if (sinkbb == gimple_bb (use))
> >>             *togsi = gsi_for_stmt (use);
> >>           else
> >> --
> >> 2.31.1
> >>