public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
From: Ajit Agarwal <aagarwa1@linux.ibm.com>
To: gcc-patches <gcc-patches@gcc.gnu.org>
Cc: Richard Biener <richard.guenther@gmail.com>,
	Segher Boessenkool <segher@kernel.crashing.org>,
	Peter Bergner <bergner@linux.ibm.com>,
	Jeff Law <jeffreyalaw@gmail.com>,
	Bernhard Reutner-Fischer <rep.dot.nop@gmail.com>
Subject: [PATCH v5] tree-ssa-sink: Improve code sinking pass
Date: Thu, 1 Jun 2023 12:50:08 +0530	[thread overview]
Message-ID: <cbe83266-cae1-e46c-2288-1a944e0c607b@linux.ibm.com> (raw)

Hello All:

This patch improves code sinking pass to sink statements before call to reduce
register pressure.
Review comments are incorporated.

For example :

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

Code Sinking does the following:

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

Bootstrapped regtested on powerpc64-linux-gnu.

Thanks & Regards
Ajit


tree-ssa-sink: Improve code sinking pass

Currently, code sinking will sink code after function calls.  This increases
register pressure for callee-saved registers.  The following patch improves
code sinking by placing the sunk code before calls in the use block or in
the immediate dominator of the use blocks.

2023-06-01  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>

gcc/ChangeLog:

	PR tree-optimization/81953
	* tree-ssa-sink.cc (statement_sink_location): Move statements before
	calls.
	(def_use_same_block): New function.
	(select_best_block): Add heuristics to select the best blocks in the
	immediate post dominator.

gcc/testsuite/ChangeLog:

	PR tree-optimization/81953
	* 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 | 15 +++++
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 19 ++++++
 gcc/tree-ssa-sink.cc                        | 71 ++++++++++++++++++---
 3 files changed, 95 insertions(+), 10 deletions(-)
 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..d3b79ca5803
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-20.c
@@ -0,0 +1,15 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-sink-stats" } */
+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 {l_12\s+=\s+_4\s+\+\s+f_11\(D\);\n\s+bar\s+\(\)} 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..84e7938c54f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c
@@ -0,0 +1,19 @@
+/* { 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 {l_13\s+=\s+_4\s+\+\s+f_12\(D\);\n\s+bar\s+\(\)} sink1 } } */
diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
index b1ba7a2ad6c..f1d25f1a0f8 100644
--- a/gcc/tree-ssa-sink.cc
+++ b/gcc/tree-ssa-sink.cc
@@ -171,9 +171,28 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
   return commondom;
 }
 
+/* Return TRUE if immediate uses of the defs in
+   STMT occur in the same block as STMT, FALSE otherwise.  */
+
+static bool
+def_use_same_block (gimple *stmt)
+{
+  def_operand_p def;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_DEF_OPERAND (def, stmt, iter, SSA_OP_DEF)
+    {
+      gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def));
+      if ((gimple_bb (def_stmt) == gimple_bb (stmt)))
+	return true;
+     }
+  return false;
+}
+
 /* Given EARLY_BB and LATE_BB, two blocks in a path through the dominator
    tree, return the best basic block between them (inclusive) to place
-   statements.
+   statements. The best basic block should be an immediate dominator of
+   best basic block if the use stmt is after the call.
 
    We want the most control dependent block in the shallowest loop nest.
 
@@ -190,7 +209,8 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
 static basic_block
 select_best_block (basic_block early_bb,
 		   basic_block late_bb,
-		   gimple *stmt)
+		   gimple *stmt,
+		   gimple *use)
 {
   basic_block best_bb = late_bb;
   basic_block temp_bb = late_bb;
@@ -237,7 +257,40 @@ select_best_block (basic_block early_bb,
       /* If result of comparsion is unknown, prefer EARLY_BB.
 	 Thus use !(...>=..) rather than (...<...)  */
       && !(best_bb->count * 100 >= early_bb->count * threshold))
-    return best_bb;
+    {
+      basic_block new_best_bb = get_immediate_dominator (CDI_DOMINATORS, best_bb);
+      /* Return best_bb if def and use are in same block otherwise new_best_bb.
+
+	 Things to consider:
+
+	   new_best_bb is not equal to best_bb and early_bb.
+
+	   stmt is not call.
+
+	   new_best_bb doesnt have any phis.
+
+	   use basic block is not equal to early_bb.
+
+	   use basic block post dominates to new_best_bb.
+
+	   new_best_bb dominates early_bb.  */
+      if (new_best_bb && use
+	  && new_best_bb != best_bb
+	  && new_best_bb != early_bb
+	  && !is_gimple_call (stmt)
+	  && gsi_end_p (gsi_start_phis (new_best_bb))
+	  && gimple_bb (use) != early_bb
+	  && !is_gimple_call (use)
+	  && dominated_by_p (CDI_POST_DOMINATORS, new_best_bb, gimple_bb (use))
+	  && dominated_by_p (CDI_DOMINATORS, new_best_bb, early_bb))
+	{
+	  if (def_use_same_block (use))
+	    return best_bb;
+
+	  return new_best_bb;
+	}
+	return best_bb;
+    }
 
   /* No better block found, so return EARLY_BB, which happens to be the
      statement's original block.  */
@@ -439,7 +492,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
       if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb))
 	return false;
 
-      commondom = select_best_block (frombb, commondom, stmt);
+      commondom = select_best_block (frombb, commondom, stmt, NULL);
 
       if (commondom == frombb)
 	return false;	
@@ -456,19 +509,17 @@ statement_sink_location (gimple *stmt, basic_block frombb,
 	    continue;
 	  break;
 	}
+
       use = USE_STMT (one_use);
 
       if (gimple_code (use) != GIMPLE_PHI)
 	{
-	  sinkbb = select_best_block (frombb, gimple_bb (use), stmt);
+	  sinkbb = select_best_block (frombb, gimple_bb (use), stmt, use);
 
 	  if (sinkbb == frombb)
 	    return false;
 
-	  if (sinkbb == gimple_bb (use))
-	    *togsi = gsi_for_stmt (use);
-	  else
-	    *togsi = gsi_after_labels (sinkbb);
+	  *togsi = gsi_after_labels (sinkbb);
 
 	  return true;
 	}
@@ -480,7 +531,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
   if (!sinkbb)
     return false;
   
-  sinkbb = select_best_block (frombb, sinkbb, stmt);
+  sinkbb = select_best_block (frombb, sinkbb, stmt, NULL);
   if (!sinkbb || sinkbb == frombb)
     return false;
 
-- 
2.39.1


             reply	other threads:[~2023-06-01  7:20 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-06-01  7:20 Ajit Agarwal [this message]
2023-06-01  8:36 ` Bernhard Reutner-Fischer
2023-06-02  4:54   ` Ajit Agarwal
2023-06-23  2:14     ` Peter Bergner
2023-06-23  7:49       ` Ajit Agarwal

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=cbe83266-cae1-e46c-2288-1a944e0c607b@linux.ibm.com \
    --to=aagarwa1@linux.ibm.com \
    --cc=bergner@linux.ibm.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=jeffreyalaw@gmail.com \
    --cc=rep.dot.nop@gmail.com \
    --cc=richard.guenther@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).