[PATCH] Fix PR63184

[PATCH] Fix PR63184

[Richard Biener]

The following fixes PR63184 by using tree-affine to resolve pointer
comparisons.  Instead of trying to stick this into a match.pd pattern
the following does this in the more constrained forwprop environment.

I've only implemented the cases where the comparison resolves to a
compile-time value, not the case where for example &a[i] < &a[j]
could be simplified to i < j.  I'm not sure I can trust the
tree-affine machinery enough here to do that.

Both testcases require some CSE to happen thus the first forwprop
pass doesn't catch it.

Bootstrap & regtest running on x86_64-unknown-linux-gnu.

I'll collect some statistics from bootstrap.

Richard.

From 79e88f7d31def4c49fe0b401e7fda408ef447710 Mon Sep 17 00:00:00 2001
From: Richard Guenther <rguenther@suse.de>
Date: Fri, 7 Dec 2018 10:47:07 +0100
Subject: [PATCH] fix-pr63184

2018-12-07  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/63184
	* tree-ssa-forwprop.c: Include tree-affine.h.
	(ttacache): New global.
	(forward_propagate_into_comparison_1): Use tree-affine to
	resolve pointer comparisons.
	(pass_forwprop::execute): Release ttacache.

	* c-c++-common/pr19807-2.c: Remove XFAIL.
	* c-c++-common/pr19807-3.c: Likewise.

diff --git a/gcc/testsuite/c-c++-common/pr19807-2.c b/gcc/testsuite/c-c++-common/pr19807-2.c
index d2c010140d0..18949a9bc5a 100644
--- a/gcc/testsuite/c-c++-common/pr19807-2.c
+++ b/gcc/testsuite/c-c++-common/pr19807-2.c
@@ -1,6 +1,5 @@
-/* Some targets can optimize this on RTL.  */
-/* { dg-do link { target { x86_64-*-* i?86-*-* } } } */
-/* { dg-options "-O -fdump-tree-optimized" } */
+/* { dg-do link } */
+/* { dg-options "-O -fdump-tree-forwprop2" } */
 
 extern void link_error(void);
 int i;
@@ -12,4 +11,4 @@ int main()
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-not "link_error" "optimized" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-not "link_error" "forwprop2" } } */
diff --git a/gcc/testsuite/c-c++-common/pr19807-3.c b/gcc/testsuite/c-c++-common/pr19807-3.c
index bb7f9827725..f6a1531677f 100644
--- a/gcc/testsuite/c-c++-common/pr19807-3.c
+++ b/gcc/testsuite/c-c++-common/pr19807-3.c
@@ -1,6 +1,5 @@
-/* Some targets can optimize this on RTL.  */
-/* { dg-do link { target { x86_64-*-* i?86-*-* } } } */
-/* { dg-options "-O -fdump-tree-optimized" } */
+/* { dg-do link } */
+/* { dg-options "-O -fdump-tree-forwprop2" } */
 
 extern void link_error(void);
 int i;
@@ -12,4 +11,4 @@ int main()
   return 0;
 }
 
-/* { dg-final { scan-tree-dump-not "link_error" "optimized" { xfail *-*-* } } } */
+/* { dg-final { scan-tree-dump-not "link_error" "forwprop2" } } */
diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c
index 7449eaf86ae..08e41e2d85d 100644
--- a/gcc/tree-ssa-forwprop.c
+++ b/gcc/tree-ssa-forwprop.c
@@ -48,6 +48,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "optabs-tree.h"
 #include "tree-vector-builder.h"
 #include "vec-perm-indices.h"
+#include "tree-affine.h"
 
 /* This pass propagates the RHS of assignment statements into use
    sites of the LHS of the assignment.  It's basically a specialized
@@ -184,6 +185,8 @@ static tree rhs_to_tree (tree type, gimple *stmt);
 
 static bitmap to_purge;
 
+static hash_map<tree, name_expansion *> *ttacache;
+
 /* Const-and-copy lattice.  */
 static vec<tree> lattice;
 
@@ -459,9 +462,72 @@ forward_propagate_into_comparison_1 (gimple *stmt,
   /* If that wasn't successful either, try both operands.  */
   if (rhs0 != NULL_TREE
       && rhs1 != NULL_TREE)
-    tmp = combine_cond_expr_cond (stmt, code, type,
-				  rhs0, rhs1,
-				  !(single_use0_p && single_use1_p));
+    {
+      tmp = combine_cond_expr_cond (stmt, code, type,
+				    rhs0, rhs1,
+				    !(single_use0_p && single_use1_p));
+      if (tmp)
+	return tmp;
+    }
+
+  /* When comparing two pointers try harder to resolve it by expanding
+     definitions (albeit not using our lattice) and looking at the
+     difference using the affine machinery.  */
+  if (POINTER_TYPE_P (TREE_TYPE (op0))
+      && TREE_CODE (op0) == SSA_NAME
+      && TREE_CODE (op1) == SSA_NAME)
+    {
+      aff_tree aff0, aff1;
+      tree_to_aff_combination_expand (op0, TREE_TYPE (op0), &aff0, &ttacache);
+      tree_to_aff_combination_expand (op1, TREE_TYPE (op1), &aff1, &ttacache);
+      aff_combination_scale (&aff1, -1);
+      aff_combination_add (&aff0, &aff1);
+      if (aff_combination_const_p (&aff0))
+	{
+	  /* Pointer difference is to be interpreted signed.  */
+	  poly_widest_int off = wi::sext (aff0.offset,
+					  TYPE_PRECISION (TREE_TYPE (op0)));
+	  if (known_eq (off, 0))
+	    switch (code)
+	      {
+	      case EQ_EXPR:
+	      case LE_EXPR:
+	      case GE_EXPR:
+	        return constant_boolean_node (true, type);
+	      case NE_EXPR:
+	      case LT_EXPR:
+	      case GT_EXPR:
+		return constant_boolean_node (false, type);
+	      default:;
+	      }
+	  else if (known_lt (off, 0))
+	    switch (code)
+	      {
+	      case LT_EXPR:
+	      case LE_EXPR:
+	      case NE_EXPR:
+	        return constant_boolean_node (true, type);
+	      case EQ_EXPR:
+	      case GE_EXPR:
+	      case GT_EXPR:
+	        return constant_boolean_node (false, type);
+	      default:;
+	      }
+	  else if (known_gt (off, 0))
+	    switch (code)
+	      {
+	      case LT_EXPR:
+	      case LE_EXPR:
+	      case NE_EXPR:
+	        return constant_boolean_node (false, type);
+	      case EQ_EXPR:
+	      case GE_EXPR:
+	      case GT_EXPR:
+	        return constant_boolean_node (true, type);
+	      default:;
+	      }
+	}
+    }
 
   return tmp;
 }
@@ -2585,6 +2651,8 @@ pass_forwprop::execute (function *fun)
     }
   free (postorder);
   lattice.release ();
+  delete ttacache;
+  ttacache = NULL;
 
   /* Fixup stmts that became noreturn calls.  This may require splitting
      blocks and thus isn't possible during the walk.  Do this

Re: [PATCH] Fix PR63184

[Richard Biener]

On Fri, 7 Dec 2018, Richard Biener wrote:

> 
> The following fixes PR63184 by using tree-affine to resolve pointer
> comparisons.  Instead of trying to stick this into a match.pd pattern
> the following does this in the more constrained forwprop environment.
> 
> I've only implemented the cases where the comparison resolves to a
> compile-time value, not the case where for example &a[i] < &a[j]
> could be simplified to i < j.  I'm not sure I can trust the
> tree-affine machinery enough here to do that.
> 
> Both testcases require some CSE to happen thus the first forwprop
> pass doesn't catch it.
> 
> Bootstrap & regtest running on x86_64-unknown-linux-gnu.
> 
> I'll collect some statistics from bootstrap.

Somewhat depressing.  There's a single instance in
libiberty/rust-demangle.c that gets resolved (a ordered compare).
This instance triggers 4 times during a c,c++ bootstrap compared
to 258098 affine expansion combinations tried.

It doesn't trigger in tramp3d at all (just to try a C++ code base).

I suspect the cases in PR63184 are arcane enough and usually we
have simpler addresses that are resolved with the existing
patterns.

I'll attach the patch to the PR and leave it alone.

Richard.

> Richard.
> 
> From 79e88f7d31def4c49fe0b401e7fda408ef447710 Mon Sep 17 00:00:00 2001
> From: Richard Guenther <rguenther@suse.de>
> Date: Fri, 7 Dec 2018 10:47:07 +0100
> Subject: [PATCH] fix-pr63184
> 
> 2018-12-07  Richard Biener  <rguenther@suse.de>
> 
> 	PR tree-optimization/63184
> 	* tree-ssa-forwprop.c: Include tree-affine.h.
> 	(ttacache): New global.
> 	(forward_propagate_into_comparison_1): Use tree-affine to
> 	resolve pointer comparisons.
> 	(pass_forwprop::execute): Release ttacache.
> 
> 	* c-c++-common/pr19807-2.c: Remove XFAIL.
> 	* c-c++-common/pr19807-3.c: Likewise.
> 
> diff --git a/gcc/testsuite/c-c++-common/pr19807-2.c b/gcc/testsuite/c-c++-common/pr19807-2.c
> index d2c010140d0..18949a9bc5a 100644
> --- a/gcc/testsuite/c-c++-common/pr19807-2.c
> +++ b/gcc/testsuite/c-c++-common/pr19807-2.c
> @@ -1,6 +1,5 @@
> -/* Some targets can optimize this on RTL.  */
> -/* { dg-do link { target { x86_64-*-* i?86-*-* } } } */
> -/* { dg-options "-O -fdump-tree-optimized" } */
> +/* { dg-do link } */
> +/* { dg-options "-O -fdump-tree-forwprop2" } */
>  
>  extern void link_error(void);
>  int i;
> @@ -12,4 +11,4 @@ int main()
>    return 0;
>  }
>  
> -/* { dg-final { scan-tree-dump-not "link_error" "optimized" { xfail *-*-* } } } */
> +/* { dg-final { scan-tree-dump-not "link_error" "forwprop2" } } */
> diff --git a/gcc/testsuite/c-c++-common/pr19807-3.c b/gcc/testsuite/c-c++-common/pr19807-3.c
> index bb7f9827725..f6a1531677f 100644
> --- a/gcc/testsuite/c-c++-common/pr19807-3.c
> +++ b/gcc/testsuite/c-c++-common/pr19807-3.c
> @@ -1,6 +1,5 @@
> -/* Some targets can optimize this on RTL.  */
> -/* { dg-do link { target { x86_64-*-* i?86-*-* } } } */
> -/* { dg-options "-O -fdump-tree-optimized" } */
> +/* { dg-do link } */
> +/* { dg-options "-O -fdump-tree-forwprop2" } */
>  
>  extern void link_error(void);
>  int i;
> @@ -12,4 +11,4 @@ int main()
>    return 0;
>  }
>  
> -/* { dg-final { scan-tree-dump-not "link_error" "optimized" { xfail *-*-* } } } */
> +/* { dg-final { scan-tree-dump-not "link_error" "forwprop2" } } */
> diff --git a/gcc/tree-ssa-forwprop.c b/gcc/tree-ssa-forwprop.c
> index 7449eaf86ae..08e41e2d85d 100644
> --- a/gcc/tree-ssa-forwprop.c
> +++ b/gcc/tree-ssa-forwprop.c
> @@ -48,6 +48,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "optabs-tree.h"
>  #include "tree-vector-builder.h"
>  #include "vec-perm-indices.h"
> +#include "tree-affine.h"
>  
>  /* This pass propagates the RHS of assignment statements into use
>     sites of the LHS of the assignment.  It's basically a specialized
> @@ -184,6 +185,8 @@ static tree rhs_to_tree (tree type, gimple *stmt);
>  
>  static bitmap to_purge;
>  
> +static hash_map<tree, name_expansion *> *ttacache;
> +
>  /* Const-and-copy lattice.  */
>  static vec<tree> lattice;
>  
> @@ -459,9 +462,72 @@ forward_propagate_into_comparison_1 (gimple *stmt,
>    /* If that wasn't successful either, try both operands.  */
>    if (rhs0 != NULL_TREE
>        && rhs1 != NULL_TREE)
> -    tmp = combine_cond_expr_cond (stmt, code, type,
> -				  rhs0, rhs1,
> -				  !(single_use0_p && single_use1_p));
> +    {
> +      tmp = combine_cond_expr_cond (stmt, code, type,
> +				    rhs0, rhs1,
> +				    !(single_use0_p && single_use1_p));
> +      if (tmp)
> +	return tmp;
> +    }
> +
> +  /* When comparing two pointers try harder to resolve it by expanding
> +     definitions (albeit not using our lattice) and looking at the
> +     difference using the affine machinery.  */
> +  if (POINTER_TYPE_P (TREE_TYPE (op0))
> +      && TREE_CODE (op0) == SSA_NAME
> +      && TREE_CODE (op1) == SSA_NAME)
> +    {
> +      aff_tree aff0, aff1;
> +      tree_to_aff_combination_expand (op0, TREE_TYPE (op0), &aff0, &ttacache);
> +      tree_to_aff_combination_expand (op1, TREE_TYPE (op1), &aff1, &ttacache);
> +      aff_combination_scale (&aff1, -1);
> +      aff_combination_add (&aff0, &aff1);
> +      if (aff_combination_const_p (&aff0))
> +	{
> +	  /* Pointer difference is to be interpreted signed.  */
> +	  poly_widest_int off = wi::sext (aff0.offset,
> +					  TYPE_PRECISION (TREE_TYPE (op0)));
> +	  if (known_eq (off, 0))
> +	    switch (code)
> +	      {
> +	      case EQ_EXPR:
> +	      case LE_EXPR:
> +	      case GE_EXPR:
> +	        return constant_boolean_node (true, type);
> +	      case NE_EXPR:
> +	      case LT_EXPR:
> +	      case GT_EXPR:
> +		return constant_boolean_node (false, type);
> +	      default:;
> +	      }
> +	  else if (known_lt (off, 0))
> +	    switch (code)
> +	      {
> +	      case LT_EXPR:
> +	      case LE_EXPR:
> +	      case NE_EXPR:
> +	        return constant_boolean_node (true, type);
> +	      case EQ_EXPR:
> +	      case GE_EXPR:
> +	      case GT_EXPR:
> +	        return constant_boolean_node (false, type);
> +	      default:;
> +	      }
> +	  else if (known_gt (off, 0))
> +	    switch (code)
> +	      {
> +	      case LT_EXPR:
> +	      case LE_EXPR:
> +	      case NE_EXPR:
> +	        return constant_boolean_node (false, type);
> +	      case EQ_EXPR:
> +	      case GE_EXPR:
> +	      case GT_EXPR:
> +	        return constant_boolean_node (true, type);
> +	      default:;
> +	      }
> +	}
> +    }
>  
>    return tmp;
>  }
> @@ -2585,6 +2651,8 @@ pass_forwprop::execute (function *fun)
>      }
>    free (postorder);
>    lattice.release ();
> +  delete ttacache;
> +  ttacache = NULL;
>  
>    /* Fixup stmts that became noreturn calls.  This may require splitting
>       blocks and thus isn't possible during the walk.  Do this
> 

-- 
Richard Biener <rguenther@suse.de>
SUSE LINUX GmbH, GF: Felix Imendoerffer, Jane Smithard, Graham Norton, HRB 21284 (AG Nuernberg)

Re: [PATCH] Fix PR63184

[Jeff Law]

On 12/7/18 3:55 AM, Richard Biener wrote:
> On Fri, 7 Dec 2018, Richard Biener wrote:
> 
>>
>> The following fixes PR63184 by using tree-affine to resolve pointer
>> comparisons.  Instead of trying to stick this into a match.pd pattern
>> the following does this in the more constrained forwprop environment.
>>
>> I've only implemented the cases where the comparison resolves to a
>> compile-time value, not the case where for example &a[i] < &a[j]
>> could be simplified to i < j.  I'm not sure I can trust the
>> tree-affine machinery enough here to do that.
>>
>> Both testcases require some CSE to happen thus the first forwprop
>> pass doesn't catch it.
>>
>> Bootstrap & regtest running on x86_64-unknown-linux-gnu.
>>
>> I'll collect some statistics from bootstrap.
> 
> Somewhat depressing.  There's a single instance in
> libiberty/rust-demangle.c that gets resolved (a ordered compare).
> This instance triggers 4 times during a c,c++ bootstrap compared
> to 258098 affine expansion combinations tried.
> 
> It doesn't trigger in tramp3d at all (just to try a C++ code base).
> 
> I suspect the cases in PR63184 are arcane enough and usually we
> have simpler addresses that are resolved with the existing
> patterns.
> 
> I'll attach the patch to the PR and leave it alone.
Seems reasonable to me as well.  It's originally your BZ and somewhere
in it I think you indicated you didn't think it was terribly important.

I'd suggest pushing it out to P4.  But I know you don't like that, so I
won't actually do it :-)

Jeff