* PATCH] tree-ssa-sink: Add heuristics for code sinking @ 2023-04-14 8:41 Ajit Agarwal 2023-04-14 8:59 ` Richard Biener 0 siblings, 1 reply; 4+ messages in thread From: Ajit Agarwal @ 2023-04-14 8:41 UTC (permalink / raw) To: gcc-patches; +Cc: Segher Boessenkool, Peter Bergner, Jeff Law 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; + if (sinkbb == gimple_bb (use)) *togsi = gsi_for_stmt (use); else -- 2.31.1 ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: PATCH] tree-ssa-sink: Add heuristics for code sinking 2023-04-14 8:41 PATCH] tree-ssa-sink: Add heuristics for code sinking Ajit Agarwal @ 2023-04-14 8:59 ` Richard Biener 2023-04-14 10:07 ` Ajit Agarwal 0 siblings, 1 reply; 4+ messages in thread From: Richard Biener @ 2023-04-14 8:59 UTC (permalink / raw) To: Ajit Agarwal; +Cc: gcc-patches, Segher Boessenkool, Peter Bergner, Jeff Law 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 > ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: PATCH] tree-ssa-sink: Add heuristics for code sinking 2023-04-14 8:59 ` Richard Biener @ 2023-04-14 10:07 ` Ajit Agarwal 2023-04-14 11:56 ` Richard Biener 0 siblings, 1 reply; 4+ messages in thread From: Ajit Agarwal @ 2023-04-14 10:07 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches, Segher Boessenkool, Peter Bergner, Jeff Law 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); -- 2.31.1 > Richard. > >> if (sinkbb == gimple_bb (use)) >> *togsi = gsi_for_stmt (use); >> else >> -- >> 2.31.1 >> ^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: PATCH] tree-ssa-sink: Add heuristics for code sinking 2023-04-14 10:07 ` Ajit Agarwal @ 2023-04-14 11:56 ` Richard Biener 0 siblings, 0 replies; 4+ messages in thread From: Richard Biener @ 2023-04-14 11:56 UTC (permalink / raw) To: Ajit Agarwal; +Cc: gcc-patches, Segher Boessenkool, Peter Bergner, Jeff Law 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 > >> ^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2023-04-14 11:56 UTC | newest] Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2023-04-14 8:41 PATCH] tree-ssa-sink: Add heuristics for code sinking Ajit Agarwal 2023-04-14 8:59 ` Richard Biener 2023-04-14 10:07 ` Ajit Agarwal 2023-04-14 11:56 ` Richard Biener
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).