[committed] [PR tree-optimization/80520] Throttle path splitting slightly.

[committed] [PR tree-optimization/80520] Throttle path splitting slightly.

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 1389 bytes --]



This is a pre-req for fixing 80520.  Essentially the goal here is to
keep the key code in this form:

  <bb 3>
  [ ... ]
  if (_20 != 0)
    goto <bb 5>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 4> [local count: 531502203]:
  _18 = _25 ^ 2567483615;

  <bb 5> [local count: 1063004407]:
  # prephitmp_49 = PHI <_25(3), _18(4)>
  _2 = (void *) ivtmp.8_30;
  MEM[base: _2, offset: 0B] = prephitmp_49;
  ivtmp.8_29 = ivtmp.8_30 + 8;
  if (ivtmp.8_29 != _6)
    goto <bb 3>; [98.99%]
  else
    goto <bb 6>; [1.01%]


Split-paths wants to duplicate bb5 into bb4.  It's just not all that
profitable to do so.  We can get ever-so-slightly better code on a
target like microblaze and perhaps others with delay slots and no
conditional move/execution capabilities.  But that seems more like
something we should be tackling at the RTL level.

To finish fixing 80520 we will need to improve the RTL if-conversion
where we presumably can cost things and make a good choice between the
branchy code we have vs straightline code with a conditional move or
conditional execution.  I'm not tackling that yet.

Note that split-path-5 has the same basic structure.  A half-diamond
with a single statement in the middle block that should be trivially
if-convertable if profitable.  So I adjusted that testcase.

Bootstrapped and regression tested on x86_64.  Installing on the trunk
momentarily.


[-- Attachment #2: P --]
[-- Type: text/plain, Size: 5771 bytes --]

commit d90b13427e4940adabc4320c68ca88513dee2eef
Author: Jeff Law <law@redhat.com>
Date:   Mon Dec 10 21:46:41 2018 -0700

            PR tree-optimization/80520
            * gimple-ssa-split-paths.c (is_feasible_trace): Recognize half
            diamonds that are likely if convertable.
    
            * gcc.dg/tree-ssa/split-path-5.c: Update expected output.
            * gcc.dg/tree-ssa/split-path-11.c: New test.

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 14c52ad64be..eddcdc3f843 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2018-12-10  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/80520
+	* gimple-ssa-split-paths.c (is_feasible_trace): Recognize half
+	diamonds that are likely if convertable.
+
 2018-12-10  Martin Sebor  <msebor@redhat.com>
 
 	PR tree-optimization/86196
diff --git a/gcc/gimple-ssa-split-paths.c b/gcc/gimple-ssa-split-paths.c
index a8515119ce5..91596526045 100644
--- a/gcc/gimple-ssa-split-paths.c
+++ b/gcc/gimple-ssa-split-paths.c
@@ -203,6 +203,98 @@ is_feasible_trace (basic_block bb)
 	}
     }
 
+  /* Canonicalize the form.  */
+  if (num_stmts_in_pred1 == 0 && num_stmts_in_pred2 == 1)
+    {
+      std::swap (pred1, pred2);
+      std::swap (num_stmts_in_pred1, num_stmts_in_pred2);
+    }
+
+  /* Another variant.  This one is half-diamond.  */
+  if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 0
+      && dominated_by_p (CDI_DOMINATORS, pred1, pred2))
+    {
+      gimple *stmt1 = last_and_only_stmt (pred1);
+
+      /* The only statement in PRED1 must be an assignment that is
+	 not a good candidate for if-conversion.   This may need some
+	 generalization.  */
+      if (stmt1 && gimple_code (stmt1) == GIMPLE_ASSIGN)
+	{
+	  enum tree_code code1 = gimple_assign_rhs_code (stmt1);
+
+	  if (!poor_ifcvt_candidate_code (code1))
+	    {
+	      tree lhs1 = gimple_assign_lhs (stmt1);
+	      tree rhs1 = gimple_assign_rhs1 (stmt1);
+
+	      gimple_stmt_iterator gsi;
+	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+		{
+		  gimple *phi = gsi_stmt (gsi);
+		  if ((gimple_phi_arg_def (phi, 0) == lhs1
+		       && gimple_phi_arg_def (phi, 1) == rhs1)
+		      || (gimple_phi_arg_def (phi, 1) == lhs1
+			  && gimple_phi_arg_def (phi, 0) == rhs1))
+		    {
+		      if (dump_file && (dump_flags & TDF_DETAILS))
+			fprintf (dump_file,
+				 "Block %d appears to be a join point for "
+				 "if-convertable half-diamond.\n",
+				 bb->index);
+		      return false;
+		    }
+		}
+	    }
+	}
+    }
+
+  /* Canonicalize the form.  */
+  if (num_stmts_in_pred1 == 0 && num_stmts_in_pred2 == 1)
+    {
+      std::swap (pred1, pred2);
+      std::swap (num_stmts_in_pred1, num_stmts_in_pred2);
+    }
+
+  /* Another variant.  This one is half-diamond.  */
+  if (num_stmts_in_pred1 == 1 && num_stmts_in_pred2 == 0
+      && dominated_by_p (CDI_DOMINATORS, pred1, pred2))
+    {
+      gimple *stmt1 = last_and_only_stmt (pred1);
+
+      /* The only statement in PRED1 must be an assignment that is
+	 not a good candidate for if-conversion.   This may need some
+	 generalization.  */
+      if (stmt1 && gimple_code (stmt1) == GIMPLE_ASSIGN)
+	{
+	  enum tree_code code1 = gimple_assign_rhs_code (stmt1);
+
+	  if (!poor_ifcvt_candidate_code (code1))
+	    {
+	      tree lhs1 = gimple_assign_lhs (stmt1);
+	      tree rhs1 = gimple_assign_rhs1 (stmt1);
+
+	      gimple_stmt_iterator gsi;
+	      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+		{
+		  gimple *phi = gsi_stmt (gsi);
+		  if ((gimple_phi_arg_def (phi, 0) == lhs1
+		       && gimple_phi_arg_def (phi, 1) == rhs1)
+		      || (gimple_phi_arg_def (phi, 1) == lhs1
+			  && gimple_phi_arg_def (phi, 0) == rhs1))
+		    {
+		      if (dump_file && (dump_flags & TDF_DETAILS))
+			fprintf (dump_file,
+				 "Block %d appears to be a join point for "
+				 "if-convertable half-diamond.\n",
+				 bb->index);
+		      return false;
+		    }
+		}
+	    }
+	}
+    }
+
   /* If the joiner has no PHIs with useful uses there is zero chance
      of CSE/DCE/jump-threading possibilities exposed by duplicating it.  */
   bool found_useful_phi = false;
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 43675b9adb0..0fde3cb395a 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2018-12-10  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/80520
+	* gcc.dg/tree-ssa/split-path-5.c: Update expected output.
+	* gcc.dg/tree-ssa/split-path-11.c: New test.
+
 2018-12-10  Steven G. Kargl  <kargl@gcc.gnu.org>
 
 	PR fortran/97922
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
new file mode 100644
index 00000000000..f94f1a84e2c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */
+
+void foo(unsigned long *M)
+{
+  for (unsigned long k = 0; k < 227; ++k)
+    {
+      unsigned long y =
+	((M[k] & 0xffffffff80000000) | (M[k + 1] & 0x7fffffff));
+      M[k] = (M[k + 397] ^ (y >> 1) ^ ((y & 1) ? 2567483615 : 0));
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "join point for if-convertable half-diamond" 1 "split-paths" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c b/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c
index 95aabdaf6be..83141a716ed 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c
@@ -41,4 +41,4 @@ bmhi_init (const char *pattern)
     }
 }
 
-/* { dg-final { scan-tree-dump-times "Duplicating join block" 1 "split-paths" } } */
+/* { dg-final { scan-tree-dump-times "join point for if-convertable half-diamond" 1 "split-paths" } } */

Re: [committed] [PR tree-optimization/80520] Throttle path splitting slightly.

[Richard Biener]

On Tue, Dec 11, 2018 at 5:56 AM Jeff Law <law@redhat.com> wrote:
>
>
>
> This is a pre-req for fixing 80520.  Essentially the goal here is to
> keep the key code in this form:
>
>   <bb 3>
>   [ ... ]
>   if (_20 != 0)
>     goto <bb 5>; [50.00%]
>   else
>     goto <bb 4>; [50.00%]
>
>   <bb 4> [local count: 531502203]:
>   _18 = _25 ^ 2567483615;
>
>   <bb 5> [local count: 1063004407]:
>   # prephitmp_49 = PHI <_25(3), _18(4)>
>   _2 = (void *) ivtmp.8_30;
>   MEM[base: _2, offset: 0B] = prephitmp_49;
>   ivtmp.8_29 = ivtmp.8_30 + 8;
>   if (ivtmp.8_29 != _6)
>     goto <bb 3>; [98.99%]
>   else
>     goto <bb 6>; [1.01%]
>
>
> Split-paths wants to duplicate bb5 into bb4.  It's just not all that
> profitable to do so.  We can get ever-so-slightly better code on a
> target like microblaze and perhaps others with delay slots and no
> conditional move/execution capabilities.  But that seems more like
> something we should be tackling at the RTL level.
>
> To finish fixing 80520 we will need to improve the RTL if-conversion
> where we presumably can cost things and make a good choice between the
> branchy code we have vs straightline code with a conditional move or
> conditional execution.  I'm not tackling that yet.
>
> Note that split-path-5 has the same basic structure.  A half-diamond
> with a single statement in the middle block that should be trivially
> if-convertable if profitable.  So I adjusted that testcase.
>
> Bootstrapped and regression tested on x86_64.  Installing on the trunk
> momentarily.

You seem to have committed two copies of the changes?

Richard.

[PATCH] Fix up split-path-11.c testcase (Re: [committed] [PR tree-optimization/80520] Throttle path splitting slightly.)

[Jakub Jelinek]

On Mon, Dec 10, 2018 at 09:56:46PM -0700, Jeff Law wrote:
> commit d90b13427e4940adabc4320c68ca88513dee2eef
> Author: Jeff Law <law@redhat.com>
> Date:   Mon Dec 10 21:46:41 2018 -0700
> 
>             PR tree-optimization/80520
>             * gimple-ssa-split-paths.c (is_feasible_trace): Recognize half
>             diamonds that are likely if convertable.
>     
>             * gcc.dg/tree-ssa/split-path-5.c: Update expected output.
>             * gcc.dg/tree-ssa/split-path-11.c: New test.
> 
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
> @@ -0,0 +1,14 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */
> +
> +void foo(unsigned long *M)
> +{
> +  for (unsigned long k = 0; k < 227; ++k)
> +    {
> +      unsigned long y =
> +	((M[k] & 0xffffffff80000000) | (M[k + 1] & 0x7fffffff));
> +      M[k] = (M[k + 397] ^ (y >> 1) ^ ((y & 1) ? 2567483615 : 0));
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump-times "join point for if-convertable half-diamond" 1 "split-paths" } } */

This testcase fails on ILP32 targets like i?86-linux*.

Fixed thusly, ok for trunk?

2018-12-11  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/80520
	* gcc.dg/tree-ssa/split-path-11.c (foo): Make the test ilp32 target
	clean.

--- gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c.jj	2018-12-11 11:02:09.009065808 +0100
+++ gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c	2018-12-11 18:10:33.811169259 +0100
@@ -1,13 +1,13 @@
 /* { dg-do compile } */
 /* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */
 
-void foo(unsigned long *M)
+void foo(unsigned long long *M)
 {
-  for (unsigned long k = 0; k < 227; ++k)
+  for (unsigned long long k = 0; k < 227; ++k)
     {
-      unsigned long y =
-	((M[k] & 0xffffffff80000000) | (M[k + 1] & 0x7fffffff));
-      M[k] = (M[k + 397] ^ (y >> 1) ^ ((y & 1) ? 2567483615 : 0));
+      unsigned long long y =
+	((M[k] & 0xffffffff80000000ULL) | (M[k + 1] & 0x7fffffffULL));
+      M[k] = (M[k + 397] ^ (y >> 1) ^ ((y & 1) ? 2567483615ULL : 0));
     }
 }
 


	Jakub

Re: [PATCH] Fix up split-path-11.c testcase (Re: [committed] [PR tree-optimization/80520] Throttle path splitting slightly.)

[Jeff Law]

On 12/11/18 10:15 AM, Jakub Jelinek wrote:
> On Mon, Dec 10, 2018 at 09:56:46PM -0700, Jeff Law wrote:
>> commit d90b13427e4940adabc4320c68ca88513dee2eef
>> Author: Jeff Law <law@redhat.com>
>> Date:   Mon Dec 10 21:46:41 2018 -0700
>>
>>             PR tree-optimization/80520
>>             * gimple-ssa-split-paths.c (is_feasible_trace): Recognize half
>>             diamonds that are likely if convertable.
>>     
>>             * gcc.dg/tree-ssa/split-path-5.c: Update expected output.
>>             * gcc.dg/tree-ssa/split-path-11.c: New test.
>>
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/tree-ssa/split-path-11.c
>> @@ -0,0 +1,14 @@
>> +/* { dg-do compile } */
>> +/* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */
>> +
>> +void foo(unsigned long *M)
>> +{
>> +  for (unsigned long k = 0; k < 227; ++k)
>> +    {
>> +      unsigned long y =
>> +	((M[k] & 0xffffffff80000000) | (M[k + 1] & 0x7fffffff));
>> +      M[k] = (M[k + 397] ^ (y >> 1) ^ ((y & 1) ? 2567483615 : 0));
>> +    }
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "join point for if-convertable half-diamond" 1 "split-paths" } } */
> 
> This testcase fails on ILP32 targets like i?86-linux*.
> 
> Fixed thusly, ok for trunk?
> 
> 2018-12-11  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR tree-optimization/80520
> 	* gcc.dg/tree-ssa/split-path-11.c (foo): Make the test ilp32 target
> 	clean.
Yes.  Sorry for the testing noise.
jeff

[PATCH] Fix split-path-5.c testcase (PR testsuite/88454)

[Jakub Jelinek]

Hi!

On Mon, Dec 10, 2018 at 09:56:46PM -0700, Jeff Law wrote:
> Note that split-path-5 has the same basic structure.  A half-diamond
> with a single statement in the middle block that should be trivially
> if-convertable if profitable.  So I adjusted that testcase.

The split-path-5.c testcase now fails on powerpc64*, arm*, aarch64* etc.
targets.

When looking for the difference, I found out it is a -fsigned-char vs.
-funsigned-char issue, on -funsigned-char targets we are simply compiling
something quite different.

The following patch fixes it, regtested on x86_64-linux (-m64/-m32) and
tested with cross to aarch64-linux and powerpc64-linux.  Ok for trunk?

2018-12-13  Jakub Jelinek  <jakub@redhat.com>

	PR testsuite/88454
	* gcc.dg/tree-ssa/split-path-5.c (__ctype_ptr__): Change type from
	const char * to const signed char *.
	(bmhi_init): Change pattern parameter's type the same.  Use
	__builtin_strlen instead of undeclared strlen.

--- gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c.jj	2018-12-11 11:02:09.003065907 +0100
+++ gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c	2018-12-13 08:36:26.457533278 +0100
@@ -1,16 +1,16 @@
 /* { dg-do compile } */
 /* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */
 
-const extern char *__ctype_ptr__;
+const extern signed char *__ctype_ptr__;
 typedef unsigned char uchar;
 static int patlen;
 static int skip[(0x7f * 2 + 1) + 1];
 static uchar *pat = ((void *) 0);
 void
-bmhi_init (const char *pattern)
+bmhi_init (const signed char *pattern)
 {
   int i, lastpatchar;
-  patlen = strlen (pattern);
+  patlen = __builtin_strlen (pattern);
   for (i = 0; i < patlen; i++)
     pat[i] = (
 	       {


	Jakub

Re: [PATCH] Fix split-path-5.c testcase (PR testsuite/88454)

[Segher Boessenkool]

On Thu, Dec 13, 2018 at 08:49:53AM +0100, Jakub Jelinek wrote:
> On Mon, Dec 10, 2018 at 09:56:46PM -0700, Jeff Law wrote:
> > Note that split-path-5 has the same basic structure.  A half-diamond
> > with a single statement in the middle block that should be trivially
> > if-convertable if profitable.  So I adjusted that testcase.
> 
> The split-path-5.c testcase now fails on powerpc64*, arm*, aarch64* etc.
> targets.
> 
> When looking for the difference, I found out it is a -fsigned-char vs.
> -funsigned-char issue, on -funsigned-char targets we are simply compiling
> something quite different.

Ha :-)

> The following patch fixes it, regtested on x86_64-linux (-m64/-m32) and
> tested with cross to aarch64-linux and powerpc64-linux.  Ok for trunk?

This is an obvious patch, isn't it :-)


Segher


> 2018-12-13  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR testsuite/88454
> 	* gcc.dg/tree-ssa/split-path-5.c (__ctype_ptr__): Change type from
> 	const char * to const signed char *.
> 	(bmhi_init): Change pattern parameter's type the same.  Use
> 	__builtin_strlen instead of undeclared strlen.
> 
> --- gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c.jj	2018-12-11 11:02:09.003065907 +0100
> +++ gcc/testsuite/gcc.dg/tree-ssa/split-path-5.c	2018-12-13 08:36:26.457533278 +0100
> @@ -1,16 +1,16 @@
>  /* { dg-do compile } */
>  /* { dg-options "-O2 -fsplit-paths -fdump-tree-split-paths-details -w" } */
>  
> -const extern char *__ctype_ptr__;
> +const extern signed char *__ctype_ptr__;
>  typedef unsigned char uchar;
>  static int patlen;
>  static int skip[(0x7f * 2 + 1) + 1];
>  static uchar *pat = ((void *) 0);
>  void
> -bmhi_init (const char *pattern)
> +bmhi_init (const signed char *pattern)
>  {
>    int i, lastpatchar;
> -  patlen = strlen (pattern);
> +  patlen = __builtin_strlen (pattern);
>    for (i = 0; i < patlen; i++)
>      pat[i] = (
>  	       {

Re: [PATCH] Fix split-path-5.c testcase (PR testsuite/88454)

[Jeff Law]

On 12/13/18 12:49 AM, Jakub Jelinek wrote:
> Hi!
> 
> On Mon, Dec 10, 2018 at 09:56:46PM -0700, Jeff Law wrote:
>> Note that split-path-5 has the same basic structure.  A half-diamond
>> with a single statement in the middle block that should be trivially
>> if-convertable if profitable.  So I adjusted that testcase.
> 
> The split-path-5.c testcase now fails on powerpc64*, arm*, aarch64* etc.
> targets.
> 
> When looking for the difference, I found out it is a -fsigned-char vs.
> -funsigned-char issue, on -funsigned-char targets we are simply compiling
> something quite different.
> 
> The following patch fixes it, regtested on x86_64-linux (-m64/-m32) and
> tested with cross to aarch64-linux and powerpc64-linux.  Ok for trunk?
> 
> 2018-12-13  Jakub Jelinek  <jakub@redhat.com>
> 
> 	PR testsuite/88454
> 	* gcc.dg/tree-ssa/split-path-5.c (__ctype_ptr__): Change type from
> 	const char * to const signed char *.
> 	(bmhi_init): Change pattern parameter's type the same.  Use
> 	__builtin_strlen instead of undeclared strlen.
Yea.  Interesting that we hadn't had problems with it before.  THanks
for taking care of it while I was out.

jeff