[PATCH] Fix PR63184

[Richard Biener <rguenther@suse.de>]

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