PR tree-optimization/81741

	PR tree-optimization/71947
	* tree-ssa-dom.c: Include tree-inline.h.
	(record_temporary_equivalences): Only record SSA_NAME = SSA_NAME
	equivalences if one is more expensive to compute than the other.
	* tree-ssa-scopedtables.h (class const_or_copies): Make
	record_const_or_copy_raw method private.
	(class avail_exprs_stack): New method simplify_binary_operation.
	* tree-ssa-scopedtables.c (avail_exprs_stack::lookup_avail_expr): Call
	avail_exprs_stack::simplify_binary_operation as needed.
	(avail_exprs_stack::simplify_binary_operation): New function.

	PR tree-optimization/81741
	PR tree-optimization/71947
	* gcc.dg/tree-ssa/pr81741.c: New test.
	* gcc.dg/tree-ssa/pr71947-7.c: New test.
	* gcc.dg/tree-ssa/pr71947-8.c: New test.
	* gcc.dg/tree-ssa/pr71947-9.c: New test.
	* gcc.dg/tree-ssa/pr71941-1.c: Tweak expected output.
	* gcc.dg/tree-ssa/pr71941-2.c: Tweak expected output.
	* gcc.dg/tree-ssa/pr71941-3.c: Tweak expected output.
	* gcc.dg/tree-ssa/20030922-2.c: xfail.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@251279 138bc75d-0d04-0410-961f-82ee72b054a4

13 files changed, 238 insertions, 16 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index ab85c074f24..9b941af74c6 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,17 @@
+2017-08-22  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/81741
+	PR tree-optimization/71947
+	* tree-ssa-dom.c: Include tree-inline.h.
+	(record_temporary_equivalences): Only record SSA_NAME = SSA_NAME
+	equivalences if one is more expensive to compute than the other.
+	* tree-ssa-scopedtables.h (class const_or_copies): Make
+	record_const_or_copy_raw method private.
+	(class avail_exprs_stack): New method simplify_binary_operation.
+	* tree-ssa-scopedtables.c (avail_exprs_stack::lookup_avail_expr): Call
+	avail_exprs_stack::simplify_binary_operation as needed.
+	(avail_exprs_stack::simplify_binary_operation): New function.
+
 2017-08-22  Sebastian Huber  <sebastian.huber@embedded-brains.de>
 
 	* config.gcc (powerpc-*-rtems*): Add rs6000/linux64.opt.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 17733519e0b..531d0f95ae7 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,16 @@
+2017-08-22  Jeff Law  <law@redhat.com>
+
+	PR tree-optimization/81741
+	PR tree-optimization/71947
+	* gcc.dg/tree-ssa/pr81741.c: New test.
+	* gcc.dg/tree-ssa/pr71947-7.c: New test.
+	* gcc.dg/tree-ssa/pr71947-8.c: New test.
+	* gcc.dg/tree-ssa/pr71947-9.c: New test.
+	* gcc.dg/tree-ssa/pr71941-1.c: Tweak expected output.
+	* gcc.dg/tree-ssa/pr71941-2.c: Tweak expected output.
+	* gcc.dg/tree-ssa/pr71941-3.c: Tweak expected output.
+	* gcc.dg/tree-ssa/20030922-2.c: xfail.
+
 2017-08-22  Yvan Roux  <yvan.roux@linaro.org>
 
         PR c++/80287
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030922-2.c b/gcc/testsuite/gcc.dg/tree-ssa/20030922-2.c
index 16c79da9521..172f203cf8e 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/20030922-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/20030922-2.c
@@ -20,4 +20,6 @@ rgn_rank (rtx insn1, rtx insn2)
 }
 
 /* There should be two IF conditionals.  */
-/* { dg-final { scan-tree-dump-times "if " 2 "dom2" } } */
+/* We no longer record the conditional equivalence by design, thus we
+   are unable to simplify the 3rd conditional at compile time.  */
+/* { dg-final { scan-tree-dump-times "if " 2 "dom2" { xfail *-*-* } } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c
index b03349546fd..ac8271cc574 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-1.c
@@ -14,6 +14,6 @@ int f(int x, int y)
    return ret;
 }
 
-/* { dg-final { scan-tree-dump "Folded to: ret_\[0-9\]+ = 0;"  "dom2" } } */
+/* { dg-final { scan-tree-dump "Replaced redundant expr \[^\r\n\]* with .0."  "dom2" } } */
 
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c
index de8f88b88d7..b2c09cbb021 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-2.c
@@ -13,4 +13,4 @@ int f(int x, int y)
   return ret;
 }
 
-/* { dg-final { scan-tree-dump "Folded to: ret_\[0-9\]+ = 0;"  "dom2" } } */
+/* { dg-final { scan-tree-dump "Replaced redundant expr \[^\r\n\]* with .0."  "dom2" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c
index e79847f83c8..2316f7e1c04 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-3.c
@@ -9,4 +9,5 @@ int f(int x, int y)
   return ret;
 }
 
-/* { dg-final { scan-tree-dump "Folded to: ret_\[0-9\]+ = 0;"  "dom2" } } */
+/* { dg-final { scan-tree-dump "Replaced redundant expr \[^\r\n\]* with .0."  "dom2" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c
new file mode 100644
index 00000000000..b44c064aa23
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-7.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+
+
+int f(int x, int y)
+{
+  int ret;
+  if (x == y)
+    ret = x % y;
+  else
+    ret = 1;
+
+  return ret;
+}
+/* { dg-final { scan-tree-dump "Replaced redundant expr \[^\r\n\]* with .0."  "dom2" } } */
+
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c
new file mode 100644
index 00000000000..26e5abbdc29
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-8.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+
+
+int f(int x, int y)
+{
+  int ret;
+  if (x == y)
+    ret = x / y;
+  else
+    ret = 0;
+
+  return ret;
+}
+/* { dg-final { scan-tree-dump "Replaced redundant expr \[^\r\n\]* with .1."  "dom2" } } */
+
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c
new file mode 100644
index 00000000000..22b68d5ede0
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr71947-9.c
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fno-tree-vrp -fdump-tree-dom-details" } */
+
+
+int f(int x, int y)
+{
+  int ret;
+  if (x == y)
+    ret = x & y;
+  else
+    ret = 0;
+
+  return ret;
+}
+/* { dg-final { scan-tree-dump "Replaced redundant expr \[^\r\n\]* with .\(x|y\)."  "dom2" } } */
+
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr81741.c b/gcc/testsuite/gcc.dg/tree-ssa/pr81741.c
new file mode 100644
index 00000000000..a162c3cf58f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr81741.c
@@ -0,0 +1,22 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -w -fdump-tree-dom2-details" } */
+
+#include <string.h>
+
+typedef struct string_s {
+  unsigned long size, alloc;
+  char *ptr;
+} string_t[1];
+
+# define M_ASSUME(x)                                    \
+  (! __builtin_constant_p (!!(x) || !(x)) || (x) ?      \
+   (void) 0 : __builtin_unreachable())
+
+int f(string_t s)
+{
+  M_ASSUME(strlen(s->ptr) == s->size);
+  return s->size;
+}
+
+/* { dg-final { scan-assembler-not "strlen" } } */
+
diff --git a/gcc/tree-ssa-dom.c b/gcc/tree-ssa-dom.c
index 494b472e121..407a4ef97d2 100644
--- a/gcc/tree-ssa-dom.c
+++ b/gcc/tree-ssa-dom.c
@@ -32,6 +32,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "cfgloop.h"
 #include "gimple-fold.h"
 #include "tree-eh.h"
+#include "tree-inline.h"
 #include "gimple-iterator.h"
 #include "tree-cfg.h"
 #include "tree-into-ssa.h"
@@ -776,16 +777,27 @@ record_temporary_equivalences (edge e,
 
       /* Record the simple NAME = VALUE equivalence.  */
       tree rhs = edge_info->rhs;
-      record_equality (lhs, rhs, const_and_copies);
 
-      /* We already recorded that LHS = RHS, with canonicalization,
-	 value chain following, etc.
+      /* If this is a SSA_NAME = SSA_NAME equivalence and one operand is
+	 cheaper to compute than the other, then set up the equivalence
+	 such that we replace the expensive one with the cheap one.
 
-	 We also want to record RHS = LHS, but without any canonicalization
-	 or value chain following.  */
-      if (TREE_CODE (rhs) == SSA_NAME)
-	const_and_copies->record_const_or_copy_raw (rhs, lhs,
-						    SSA_NAME_VALUE (rhs));
+	 If they are the same cost to compute, then do not record anything.  */
+      if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME)
+	{
+	  gimple *rhs_def = SSA_NAME_DEF_STMT (rhs);
+	  int rhs_cost = estimate_num_insns (rhs_def, &eni_size_weights);
+
+	  gimple *lhs_def = SSA_NAME_DEF_STMT (lhs);
+	  int lhs_cost = estimate_num_insns (lhs_def, &eni_size_weights);
+
+	  if (rhs_cost > lhs_cost)
+	    record_equality (rhs, lhs, const_and_copies);
+	  else if (rhs_cost < lhs_cost)
+	    record_equality (lhs, rhs, const_and_copies);
+	}
+      else
+	record_equality (lhs, rhs, const_and_copies);
 
       /* If LHS is an SSA_NAME and RHS is a constant integer and LHS was
 	 set via a widening type conversion, then we may be able to record
diff --git a/gcc/tree-ssa-scopedtables.c b/gcc/tree-ssa-scopedtables.c
index 7b9ca78a878..6e1fd582814 100644
--- a/gcc/tree-ssa-scopedtables.c
+++ b/gcc/tree-ssa-scopedtables.c
@@ -116,6 +116,102 @@ vuse_eq (ao_ref *, tree vuse1, unsigned int cnt, void *data)
   return NULL;
 }
 
+/* We looked for STMT in the hash table, but did not find it.
+
+   If STMT is an assignment from a binary operator, we may know something
+   about the operands relationship to each other which would allow
+   us to derive a constant value for the RHS of STMT.  */
+
+tree
+avail_exprs_stack::simplify_binary_operation (gimple *stmt,
+					      class expr_hash_elt element)
+{
+  if (is_gimple_assign (stmt))
+    {
+      struct hashable_expr *expr = element.expr ();
+      if (expr->kind == EXPR_BINARY)
+	{
+	  enum tree_code code = expr->ops.binary.op;
+
+	  switch (code)
+	    {
+	    /* For these cases, if we know the operands
+	       are equal, then we know the result.  */
+	    case MIN_EXPR:
+	    case MAX_EXPR:
+	    case BIT_IOR_EXPR:
+	    case BIT_AND_EXPR:
+	    case BIT_XOR_EXPR:
+	    case MINUS_EXPR:
+	    case TRUNC_DIV_EXPR:
+	    case CEIL_DIV_EXPR:
+	    case FLOOR_DIV_EXPR:
+	    case ROUND_DIV_EXPR:
+	    case EXACT_DIV_EXPR:
+	    case TRUNC_MOD_EXPR:
+	    case CEIL_MOD_EXPR:
+	    case FLOOR_MOD_EXPR:
+	    case ROUND_MOD_EXPR:
+	      {
+		/* Build a simple equality expr and query the hash table
+		   for it.  */
+		struct hashable_expr expr;
+		expr.type = boolean_type_node;
+		expr.kind = EXPR_BINARY;
+		expr.ops.binary.op = EQ_EXPR;
+		expr.ops.binary.opnd0 = gimple_assign_rhs1 (stmt);
+		expr.ops.binary.opnd1 = gimple_assign_rhs2 (stmt);
+		class expr_hash_elt element2 (&expr, NULL_TREE);
+		expr_hash_elt **slot
+		  = m_avail_exprs->find_slot (&element2, NO_INSERT);
+		tree result_type = TREE_TYPE (gimple_assign_lhs (stmt));
+
+		/* If the query was successful and returned a nonzero
+		   result, then we know that the operands of the binary
+		   expression are the same.  In many cases this allows
+		   us to compute a constant result of the expression
+		   at compile time, even if we do not know the exact
+		   values of the operands.  */
+		if (slot && *slot && integer_onep ((*slot)->lhs ()))
+		  {
+		    switch (code)
+		      {
+		      case MIN_EXPR:
+		      case MAX_EXPR:
+		      case BIT_IOR_EXPR:
+		      case BIT_AND_EXPR:
+			return gimple_assign_rhs1 (stmt);
+
+		      case BIT_XOR_EXPR:
+		      case MINUS_EXPR:
+		      case TRUNC_MOD_EXPR:
+		      case CEIL_MOD_EXPR:
+		      case FLOOR_MOD_EXPR:
+		      case ROUND_MOD_EXPR:
+			return build_zero_cst (result_type);
+
+		      case TRUNC_DIV_EXPR:
+		      case CEIL_DIV_EXPR:
+		      case FLOOR_DIV_EXPR:
+		      case ROUND_DIV_EXPR:
+		      case EXACT_DIV_EXPR:
+			return build_one_cst (result_type);
+
+		      default:
+			gcc_unreachable ();
+		      }
+		  }
+		break;
+	      }
+
+	      default:
+		break;
+	    }
+	}
+    }
+  return NULL_TREE;
+}
+
 /* Search for an existing instance of STMT in the AVAIL_EXPRS_STACK table.
    If found, return its LHS. Otherwise insert STMT in the table and
    return NULL_TREE.
@@ -160,6 +256,12 @@ avail_exprs_stack::lookup_avail_expr (gimple *stmt, bool insert, bool tbaa_p)
     }
   else if (*slot == NULL)
     {
+      /* If we did not find the expression in the hash table, we may still
+	 be able to produce a result for some expressions.  */
+      tree alt = avail_exprs_stack::simplify_binary_operation (stmt, element);
+      if (alt)
+	return alt;
+
       class expr_hash_elt *element2 = new expr_hash_elt (element);
       *slot = element2;
 
diff --git a/gcc/tree-ssa-scopedtables.h b/gcc/tree-ssa-scopedtables.h
index df304aedbf4..e3d7bff6913 100644
--- a/gcc/tree-ssa-scopedtables.h
+++ b/gcc/tree-ssa-scopedtables.h
@@ -156,6 +156,11 @@ class avail_exprs_stack
   vec<std::pair<expr_hash_elt_t, expr_hash_elt_t> > m_stack;
   hash_table<expr_elt_hasher> *m_avail_exprs;
 
+  /* For some assignments where the RHS is a binary operator, if we know
+     a equality relationship between the operands, we may be able to compute
+     a result, even if we don't know the exact value of the operands.  */
+  tree simplify_binary_operation (gimple *, class expr_hash_elt);
+
   /* We do not allow copying this object or initializing one
      from another.  */
   avail_exprs_stack& operator= (const avail_exprs_stack&);
@@ -185,10 +190,6 @@ class const_and_copies
      may follow the value chain for the RHS.  */
   void record_const_or_copy (tree, tree);
 
-  /* Record a single const/copy pair that can be unwound.  This version
-     does not follow the value chain for the RHS.  */
-  void record_const_or_copy_raw (tree, tree, tree);
-
   /* Special entry point when we want to provide an explicit previous
      value for the first argument.  Try to get rid of this in the future. 
 
@@ -196,6 +197,10 @@ class const_and_copies
   void record_const_or_copy (tree, tree, tree);
 
  private:
+  /* Record a single const/copy pair that can be unwound.  This version
+     does not follow the value chain for the RHS.  */
+  void record_const_or_copy_raw (tree, tree, tree);
+
   vec<tree> m_stack;
   const_and_copies& operator= (const const_and_copies&);
   const_and_copies (class const_and_copies &);