public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Richard Biener <richard.guenther@gmail.com>
To: Ajit Agarwal <aagarwa1@linux.ibm.com>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>,
	 Segher Boessenkool <segher@kernel.crashing.org>,
	Peter Bergner <bergner@linux.ibm.com>,
	 Jeff Law <jeffreyalaw@gmail.com>
Subject: Re: PATCH] tree-ssa-sink: Add heuristics for code sinking
Date: Fri, 14 Apr 2023 13:56:27 +0200	[thread overview]
Message-ID: <CAFiYyc2CbfV8Q1NhkGL6ZCaubnG6n0xygNpc21VXUUVntFZz=w@mail.gmail.com> (raw)
In-Reply-To: <575418e4-7d40-3d56-044b-fdd91a7c657a@linux.ibm.com>

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
> >>

      reply	other threads:[~2023-04-14 11:56 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-04-14  8:41 Ajit Agarwal
2023-04-14  8:59 ` Richard Biener
2023-04-14 10:07   ` Ajit Agarwal
2023-04-14 11:56     ` Richard Biener [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAFiYyc2CbfV8Q1NhkGL6ZCaubnG6n0xygNpc21VXUUVntFZz=w@mail.gmail.com' \
    --to=richard.guenther@gmail.com \
    --cc=aagarwa1@linux.ibm.com \
    --cc=bergner@linux.ibm.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=jeffreyalaw@gmail.com \
    --cc=segher@kernel.crashing.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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).