public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH] tree-ssa-sink: Improve code sinking pass.
@ 2023-04-16 13:20 Ajit Agarwal
  2023-04-29  0:11 ` Jeff Law
  0 siblings, 1 reply; 4+ messages in thread
From: Ajit Agarwal @ 2023-04-16 13:20 UTC (permalink / raw)
  To: gcc-patches; +Cc: Segher Boessenkool, Peter Bergner, Richard Biener, Jeff Law

Hello All:

This patch improves code sinking pass to sink the blocks before calls
in the use blocks or immediate dominator blocks that reduces register pressure.

Bootstrapped and regtested on powerpc64-linux-gnu.

Thanks & Regards
Ajit

	tree-ssa-sink: Improve code sinking pass.

	Code Sinking sinks the blocks after call. This increases
	register pressure for callee-saved registers. Improves
	code sinking before call in the use blocks or immediate
	dominator of use blocks.

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

gcc/ChangeLog:

	* tree-ssa-sink.cc (statement_sink_location): Modifed to
	move statements before calls.
	(block_call_p): New function.
	(def_use_same_block): New function.
	(select_best_block): Add heuristics to select the best
	blocks in the immediate post dominator.

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                        | 134 +++++++++++++++++++-
 3 files changed, 164 insertions(+), 6 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..716bc1f9257
--- /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 -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-times "Sunk statements: 5" 1 "sink" } } */
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..ff41e2ea8ae
--- /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 -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: 5" 1 "sink" } } */
diff --git a/gcc/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
index 87b1d40c174..12babf73321 100644
--- a/gcc/tree-ssa-sink.cc
+++ b/gcc/tree-ssa-sink.cc
@@ -171,6 +171,70 @@ nearest_common_dominator_of_uses (def_operand_p def_p, bool *debug_stmts)
   return commondom;
 }
 
+/* Check def and use stmts are in same block.  */
+
+bool
+def_use_same_block (gimple *use)
+{
+  use_operand_p use_p;
+  def_operand_p def_p;
+  imm_use_iterator imm_iter;
+  ssa_op_iter iter;
+
+  FOR_EACH_SSA_DEF_OPERAND (def_p, use, iter, SSA_OP_DEF)
+    {
+      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, DEF_FROM_PTR (def_p))
+	{
+	  if (is_gimple_debug (USE_STMT (use_p)))
+	    continue;
+
+	  if (use_p
+	      && (gimple_bb(USE_STMT (use_p)) == gimple_bb (use)))
+	    return true;
+	}
+     }
+  return false;
+}
+
+/* Check if the block has only calls.  */
+
+bool
+block_call_p (basic_block bb)
+{
+  int i = 0;
+  bool is_call = false;
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  gimple *last_stmt = gsi_stmt (gsi);
+
+  if (last_stmt && gimple_code (last_stmt) == GIMPLE_COND)
+    {
+      if (!gsi_end_p (gsi))
+	gsi_prev (&gsi);
+
+       for (; !gsi_end_p (gsi);)
+	 {
+	   gimple *stmt = gsi_stmt (gsi);
+
+	   if (is_gimple_debug (stmt))
+	     return false;
+
+	   if (is_gimple_call (stmt))
+	     is_call = true;
+	   else
+	     return false;
+
+	   if (!gsi_end_p (gsi))
+	     gsi_prev (&gsi);
+
+	    ++i;
+	}
+     }
+  if (is_call && i == 1)
+    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.
@@ -190,7 +254,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 = 0)
 {
   basic_block best_bb = late_bb;
   basic_block temp_bb = late_bb;
@@ -230,7 +295,28 @@ select_best_block (basic_block early_bb,
       if (threshold > 100)
 	threshold = 100;
     }
+  if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
+      && !(best_bb->count * 100 >= early_bb->count * threshold))
+    {
+      basic_block new_best_bb = get_immediate_dominator (CDI_DOMINATORS, best_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)
+	  && block_call_p (new_best_bb))
+	{
+	  if (def_use_same_block (use))
+	    return best_bb;
 
+	  return new_best_bb;
+	}
+    }
   /* If BEST_BB is at the same nesting level, then require it to have
      significantly lower execution frequency to avoid gratuitous movement.  */
   if (bb_loop_depth (best_bb) == bb_loop_depth (early_bb)
@@ -456,19 +542,55 @@ 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);
+	   gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p));
+
+	   if ((gimple_bb (def_stmt) == gimple_bb (use))
+		&& (gimple_bb (use) != sinkbb))
+	     sinkbb = gimple_bb (use);
+
+	    if (sinkbb == gimple_bb (use))
+	      {
+		gimple_stmt_iterator gsi = gsi_last_bb (sinkbb);
+		gimple *def_stmt = SSA_NAME_DEF_STMT (DEF_FROM_PTR (def_p));
+		gimple *last_stmt = gsi_stmt (gsi);
+
+		if (gsi_stmt (gsi) == use
+		    && !is_gimple_call (last_stmt)
+		    && (gimple_code (last_stmt) != GIMPLE_SWITCH)
+		    && (gimple_code (last_stmt) != GIMPLE_COND)
+		    && (gimple_code (last_stmt) != GIMPLE_GOTO)
+		    && (!gimple_vdef (use) || !def_use_same_block (def_stmt)))
+		  {
+		    if (!gsi_end_p (gsi))
+		      gsi_prev (&gsi);
+
+		    gimple *stmt = gsi_stmt (gsi);
+
+		    if (!gsi_end_p (gsi))
+		      gsi_prev (&gsi);
+
+		    if (gsi_end_p (gsi) && stmt && is_gimple_call (stmt)
+			&& gsi_end_p (gsi_start_phis (sinkbb))
+			&& !is_gimple_call (def_stmt))
+		      *togsi = gsi_for_stmt (stmt);
+		    else
+		      *togsi = gsi_for_stmt (use);
+		   }
+		else
+		  *togsi = gsi_for_stmt(use);
+	       }
+	     else
+		*togsi = gsi_after_labels (sinkbb);
 
 	  return true;
 	}
-- 
2.31.1


^ permalink raw reply	[flat|nested] 4+ messages in thread
* [PATCH] tree-ssa-sink: Improve code sinking pass
@ 2024-03-13 13:56 Ajit Agarwal
  2024-05-08 13:23 ` Richard Biener
  0 siblings, 1 reply; 4+ messages in thread
From: Ajit Agarwal @ 2024-03-13 13:56 UTC (permalink / raw)
  To: Richard Biener, Jeff Law, Kewen.Lin, Michael Meissner,
	Peter Bergner, Segher Boessenkool, David Edelsohn, gcc-patches

Hello Richard:

Currently, code sinking will sink code at the use points with loop having same
nesting depth. The following patch improves code sinking by placing the sunk
code in begining of the block after the labels.

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

tree-ssa-sink: Improve code sinking pass

Currently, code sinking will sink code at the use points with loop having same
nesting depth. The following patch improves code sinking by placing the sunk
code in begining of the block after the labels.

2024-03-13  Ajit Kumar Agarwal  <aagarwa1@linux.ibm.com>

gcc/ChangeLog:

        PR tree-optimization/81953
        * tree-ssa-sink.cc (statement_sink_location):Sink statements at
	the begining of the basic block after labels.

gcc/testsuite/ChangeLog:

        PR tree-optimization/81953
        * gcc.dg/tree-ssa/ssa-sink-21.c: New test.
---
 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c | 15 +++++++++++++++
 gcc/tree-ssa-sink.cc                        |  7 ++-----
 2 files changed, 17 insertions(+), 5 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.c

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..d3b79ca5803
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-sink-21.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/tree-ssa-sink.cc b/gcc/tree-ssa-sink.cc
index 880d6f70a80..1ec5c048fe7 100644
--- a/gcc/tree-ssa-sink.cc
+++ b/gcc/tree-ssa-sink.cc
@@ -208,7 +208,6 @@ select_best_block (basic_block early_bb,
  	 loop nest.  */
       temp_bb = get_immediate_dominator (CDI_DOMINATORS, temp_bb);
     }
-
   /* Placing a statement before a setjmp-like function would be invalid
      (it cannot be reevaluated when execution follows an abnormal edge).
      If we selected a block with abnormal predecessors, just punt.  */
@@ -430,6 +429,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
 	    continue;
 	  break;
 	}
+
       use = USE_STMT (one_use);
 
       if (gimple_code (use) != GIMPLE_PHI)
@@ -439,10 +439,7 @@ statement_sink_location (gimple *stmt, basic_block frombb,
 	  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;
 	}
-- 
2.39.3


^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2024-05-08 13:23 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-04-16 13:20 [PATCH] tree-ssa-sink: Improve code sinking pass Ajit Agarwal
2023-04-29  0:11 ` Jeff Law
2024-03-13 13:56 Ajit Agarwal
2024-05-08 13:23 ` 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).