re PR tree-optimization/88676 (missed opportunity in integer conditional)

	PR tree-optimization/88676
	* tree-ssa-phiopt.c (two_value_replacement): New function.
	(tree_ssa_phiopt_worker): Call it.

	* gcc.dg/tree-ssa/pr88676.c: New test.
	* gcc.dg/pr88676.c: New test.
	* gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto,
	allow &.

From-SVN: r267634

6 files changed, 335 insertions, 3 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 73fd246..44e9eb3 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,9 @@
 2019-01-07  Jakub Jelinek  <jakub@redhat.com>
 
+	PR tree-optimization/88676
+	* tree-ssa-phiopt.c (two_value_replacement): New function.
+	(tree_ssa_phiopt_worker): Call it.
+
 	PR sanitizer/88619
 	* cfgexpand.c (expand_stack_vars): Only align prev_offset to
 	ASAN_MIN_RED_ZONE_SIZE, not to maximum of that and alignb.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 538f7f3..5a01e0ca 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,11 @@
 2019-01-07  Jakub Jelinek  <jakub@redhat.com>
 
+	PR tree-optimization/88676
+	* gcc.dg/tree-ssa/pr88676.c: New test.
+	* gcc.dg/pr88676.c: New test.
+	* gcc.dg/tree-ssa/pr15826.c: Just verify there is no goto,
+	allow &.
+
 	PR sanitizer/88619
 	* c-c++-common/asan/pr88619.c: New test.
 
diff --git a/gcc/testsuite/gcc.dg/pr88676.c b/gcc/testsuite/gcc.dg/pr88676.c
new file mode 100644
index 0000000..b5fdd93
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr88676.c
@@ -0,0 +1,48 @@
+/* PR tree-optimization/88676 */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+#include "tree-ssa/pr88676.c"
+
+__attribute__((noipa)) void
+bar (int x, int y, int z)
+{
+  if (z != 115 && z != 116)
+    __builtin_abort ();
+  if (x == 98)
+    {
+      if (y != z)
+	__builtin_abort ();
+    }
+  else if (x != 99)
+    __builtin_abort ();
+  else if (z == 115)
+    {
+      if (y != 116)
+	__builtin_abort ();
+    }
+  else if (y != 115)
+    __builtin_abort ();
+}
+
+int
+main ()
+{
+  if (f1 (0) != 1 || f1 (1) != 2)
+    __builtin_abort ();
+  int i;
+  for (i = -12; i < 12; i++)
+    {
+      f2 (i);
+      f3 (i);
+      f4 (i);
+      f5 (i);
+      f6 (i);
+      f7 (i);
+      f8 (i);
+      f9 (i);
+      if (f10 (i) != ((i & 1) ? 84 : 85))
+	__builtin_abort ();
+    }
+  return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr15826.c b/gcc/testsuite/gcc.dg/tree-ssa/pr15826.c
index 99ac0e2..f36c209 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr15826.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr15826.c
@@ -33,4 +33,4 @@ andrew (struct s *p)
   return i;
 }
 
-/* { dg-final { scan-tree-dump-times " & | goto " 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr88676.c b/gcc/testsuite/gcc.dg/tree-ssa/pr88676.c
new file mode 100644
index 0000000..607ac6b
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr88676.c
@@ -0,0 +1,133 @@
+/* PR tree-optimization/88676 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-not " = PHI <" "optimized" } } */
+
+void bar (int, int, int);
+
+__attribute__((noipa)) int
+f1 (unsigned x)
+{
+  int r;
+  if (x >= 2)
+    __builtin_unreachable ();
+  switch (x)
+    {
+    case 0:
+      r = 1;
+      break;
+    case 1:
+      r = 2;
+      break;
+    default:
+      r = 0;
+      break;
+    }
+  return r;
+}
+
+__attribute__((noipa)) void
+f2 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x != 98)
+    y = 115;
+  else
+    y = 116;
+  bar (x, y, 116);
+}
+
+__attribute__((noipa)) void
+f3 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x == 98)
+    y = 115;
+  else
+    y = 116;
+  bar (x, y, 115);
+}
+
+__attribute__((noipa)) void
+f4 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x != 99)
+    y = 115;
+  else
+    y = 116;
+  bar (x, y, 115);
+}
+
+__attribute__((noipa)) void
+f5 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x == 99)
+    y = 115;
+  else
+    y = 116;
+  bar (x, y, 116);
+}
+
+__attribute__((noipa)) void
+f6 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x != 98)
+    y = 116;
+  else
+    y = 115;
+  bar (x, y, 115);
+}
+
+__attribute__((noipa)) void
+f7 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x == 98)
+    y = 116;
+  else
+    y = 115;
+  bar (x, y, 116);
+}
+
+__attribute__((noipa)) void
+f8 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x != 99)
+    y = 116;
+  else
+    y = 115;
+  bar (x, y, 116);
+}
+
+__attribute__((noipa)) void
+f9 (int x)
+{
+  int y;
+  x = (x & 1) + 98;
+  if (x == 99)
+    y = 116;
+  else
+    y = 115;
+  bar (x, y, 115);
+}
+
+__attribute__((noipa)) int
+f10 (int x)
+{
+  x = (x & 1) + 36;
+  if (x == 36)
+    return 85;
+  else
+    return 84;
+}
diff --git a/gcc/tree-ssa-phiopt.c b/gcc/tree-ssa-phiopt.c
index e835329..025e403 100644
--- a/gcc/tree-ssa-phiopt.c
+++ b/gcc/tree-ssa-phiopt.c
@@ -48,6 +48,8 @@ along with GCC; see the file COPYING3.  If not see
 #include "case-cfn-macros.h"
 
 static unsigned int tree_ssa_phiopt_worker (bool, bool, bool);
+static bool two_value_replacement (basic_block, basic_block, edge, gphi *,
+				   tree, tree);
 static bool conditional_replacement (basic_block, basic_block,
 				     edge, edge, gphi *, tree, tree);
 static gphi *factor_out_conditional_conversion (edge, edge, gphi *, tree, tree,
@@ -332,8 +334,11 @@ tree_ssa_phiopt_worker (bool do_store_elim, bool do_hoist_loads, bool early_p)
 	    }
 
 	  /* Do the replacement of conditional if it can be done.  */
-	  if (!early_p
-	      && conditional_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
+	  if (two_value_replacement (bb, bb1, e2, phi, arg0, arg1))
+	    cfgchanged = true;
+	  else if (!early_p
+		   && conditional_replacement (bb, bb1, e1, e2, phi,
+					       arg0, arg1))
 	    cfgchanged = true;
 	  else if (abs_replacement (bb, bb1, e1, e2, phi, arg0, arg1))
 	    cfgchanged = true;
@@ -572,6 +577,142 @@ factor_out_conditional_conversion (edge e0, edge e1, gphi *phi,
   return newphi;
 }
 
+/* Optimize
+   # x_5 in range [cst1, cst2] where cst2 = cst1 + 1
+   if (x_5 op cstN) # where op is == or != and N is 1 or 2
+     goto bb3;
+   else
+     goto bb4;
+   bb3:
+   bb4:
+   # r_6 = PHI<cst3(2), cst4(3)> # where cst3 == cst4 + 1 or cst4 == cst3 + 1
+
+   to r_6 = x_5 + (min (cst3, cst4) - cst1) or
+   r_6 = (min (cst3, cst4) + cst1) - x_5 depending on op, N and which
+   of cst3 and cst4 is smaller.  */
+
+static bool
+two_value_replacement (basic_block cond_bb, basic_block middle_bb,
+		       edge e1, gphi *phi, tree arg0, tree arg1)
+{
+  /* Only look for adjacent integer constants.  */
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (arg0))
+      || !INTEGRAL_TYPE_P (TREE_TYPE (arg1))
+      || TREE_CODE (arg0) != INTEGER_CST
+      || TREE_CODE (arg1) != INTEGER_CST
+      || (tree_int_cst_lt (arg0, arg1)
+	  ? wi::to_widest (arg0) + 1 != wi::to_widest (arg1)
+	  : wi::to_widest (arg1) + 1 != wi::to_widest (arg1)))
+    return false;
+
+  if (!empty_block_p (middle_bb))
+    return false;
+
+  gimple *stmt = last_stmt (cond_bb);
+  tree lhs = gimple_cond_lhs (stmt);
+  tree rhs = gimple_cond_rhs (stmt);
+
+  if (TREE_CODE (lhs) != SSA_NAME
+      || !INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+      || TREE_CODE (TREE_TYPE (lhs)) == BOOLEAN_TYPE
+      || TREE_CODE (rhs) != INTEGER_CST)
+    return false;
+
+  switch (gimple_cond_code (stmt))
+    {
+    case EQ_EXPR:
+    case NE_EXPR:
+      break;
+    default:
+      return false;
+    }
+
+  wide_int min, max;
+  if (get_range_info (lhs, &min, &max) != VR_RANGE
+      || min + 1 != max
+      || (wi::to_wide (rhs) != min
+	  && wi::to_wide (rhs) != max))
+    return false;
+
+  /* We need to know which is the true edge and which is the false
+     edge so that we know when to invert the condition below.  */
+  edge true_edge, false_edge;
+  extract_true_false_edges_from_block (cond_bb, &true_edge, &false_edge);
+  if ((gimple_cond_code (stmt) == EQ_EXPR)
+      ^ (wi::to_wide (rhs) == max)
+      ^ (e1 == false_edge))
+    std::swap (arg0, arg1);
+
+  tree type;
+  if (TYPE_PRECISION (TREE_TYPE (lhs)) == TYPE_PRECISION (TREE_TYPE (arg0)))
+    {
+      /* Avoid performing the arithmetics in bool type which has different
+	 semantics, otherwise prefer unsigned types from the two with
+	 the same precision.  */
+      if (TREE_CODE (TREE_TYPE (arg0)) == BOOLEAN_TYPE
+	  || !TYPE_UNSIGNED (TREE_TYPE (arg0)))
+	type = TREE_TYPE (lhs);
+      else
+	type = TREE_TYPE (arg0);
+    }
+  else if (TYPE_PRECISION (TREE_TYPE (lhs)) > TYPE_PRECISION (TREE_TYPE (arg0)))
+    type = TREE_TYPE (lhs);
+  else
+    type = TREE_TYPE (arg0);
+
+  min = wide_int::from (min, TYPE_PRECISION (type),
+			TYPE_SIGN (TREE_TYPE (lhs)));
+  wide_int a = wide_int::from (wi::to_wide (arg0), TYPE_PRECISION (type),
+			       TYPE_SIGN (TREE_TYPE (arg0)));
+  enum tree_code code;
+  wi::overflow_type ovf;
+  if (tree_int_cst_lt (arg0, arg1))
+    {
+      code = PLUS_EXPR;
+      a -= min;
+      if (!TYPE_UNSIGNED (type))
+	{
+	  /* lhs is known to be in range [min, min+1] and we want to add a
+	     to it.  Check if that operation can overflow for those 2 values
+	     and if yes, force unsigned type.  */
+	  wi::add (min + (wi::neg_p (a) ? 0 : 1), a, SIGNED, &ovf);
+	  if (ovf)
+	    type = unsigned_type_for (type);
+	}
+    }
+  else
+    {
+      code = MINUS_EXPR;
+      a += min;
+      if (!TYPE_UNSIGNED (type))
+	{
+	  /* lhs is known to be in range [min, min+1] and we want to subtract
+	     it from a.  Check if that operation can overflow for those 2
+	     values and if yes, force unsigned type.  */
+	  wi::sub (a, min + (wi::neg_p (min) ? 0 : 1), SIGNED, &ovf);
+	  if (ovf)
+	    type = unsigned_type_for (type);
+	}
+    }
+
+  tree arg = wide_int_to_tree (type, a);
+  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+  if (!useless_type_conversion_p (type, TREE_TYPE (lhs)))
+    lhs = gimplify_build1 (&gsi, NOP_EXPR, type, lhs);
+  tree new_rhs;
+  if (code == PLUS_EXPR)
+    new_rhs = gimplify_build2 (&gsi, PLUS_EXPR, type, lhs, arg);
+  else
+    new_rhs = gimplify_build2 (&gsi, MINUS_EXPR, type, arg, lhs);
+  if (!useless_type_conversion_p (TREE_TYPE (arg0), type))
+    new_rhs = gimplify_build1 (&gsi, NOP_EXPR, TREE_TYPE (arg0), new_rhs);
+
+  replace_phi_edge_with_variable (cond_bb, e1, phi, new_rhs);
+
+  /* Note that we optimized this PHI.  */
+  return true;
+}
+
 /*  The function conditional_replacement does the main work of doing the
     conditional replacement.  Return true if the replacement is done.
     Otherwise return false.