[PATCH] Optimize x == 0 && y == 0 into (x | y) == 0 in reassoc range opt (PR middle-end/35691)

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

Right now we handle x == 0 && y == 0 into (x | y) == 0
and x == -1 && y == -1 into (x & y) == -1 optimizations just in
match.pd, where it will handle the case where the && (or || if using !=)
is actually & (or |) and they are next to each other.
It doesn't handle the case when we have such comparisons as part of
a larger && or || test that is split into multiple basic blocks or
intermixed with other comparisons.

The following patch teaches optimize_range_tests to optimize even these.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2017-09-26  Jakub Jelinek  <jakub@redhat.com>

	PR middle-end/35691
	* tree-ssa-reassoc.c (update_range_test): Dump r->exp each time
	if it is different SSA_NAME.
	(optimize_range_tests_cmp_bitwise): New function.
	(optimize_range_tests): Call it.

	* gcc.dg/pr35691-5.c: New test.
	* gcc.dg/pr35691-6.c: New test.

--- gcc/tree-ssa-reassoc.c.jj	2017-09-26 09:35:15.101842092 +0200
+++ gcc/tree-ssa-reassoc.c	2017-09-26 10:18:07.600993304 +0200
@@ -2379,7 +2379,16 @@ update_range_test (struct range_entry *r
 	    r = otherrange + i;
 	  else
 	    r = otherrangep[i];
-	  fprintf (dump_file, " and %c[", r->in_p ? '+' : '-');
+	  if (r->exp
+	      && r->exp != range->exp
+	      && TREE_CODE (r->exp) == SSA_NAME)
+	    {
+	      fprintf (dump_file, " and ");
+	      print_generic_expr (dump_file, r->exp);
+	    }
+	  else
+	    fprintf (dump_file, " and");
+	  fprintf (dump_file, " %c[", r->in_p ? '+' : '-');
 	  print_generic_expr (dump_file, r->low);
 	  fprintf (dump_file, ", ");
 	  print_generic_expr (dump_file, r->high);
@@ -2880,6 +2889,134 @@ optimize_range_tests_to_bit_test (enum t
   return any_changes;
 }
 
+/* Optimize x != 0 && y != 0 && z != 0 into (x | y | z) != 0
+   and similarly x != -1 && y != -1 && y != -1 into (x & y & z) != -1.  */
+
+static bool
+optimize_range_tests_cmp_bitwise (enum tree_code opcode, int first, int length,
+				  vec<operand_entry *> *ops,
+				  struct range_entry *ranges)
+{
+  int i;
+  unsigned int b;
+  bool any_changes = false;
+  auto_vec<int, 128> buckets;
+  auto_vec<int, 32> chains;
+  auto_vec<struct range_entry *, 32> candidates;
+
+  for (i = first; i < length; i++)
+    {
+      if (ranges[i].exp == NULL_TREE
+	  || TREE_CODE (ranges[i].exp) != SSA_NAME
+	  || !ranges[i].in_p
+	  || TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) <= 1
+	  || TREE_CODE (TREE_TYPE (ranges[i].exp)) == BOOLEAN_TYPE
+	  || ranges[i].low == NULL_TREE
+	  || ranges[i].low != ranges[i].high)
+	continue;
+
+      bool zero_p = integer_zerop (ranges[i].low);
+      if (!zero_p && !integer_all_onesp (ranges[i].low))
+	continue;
+
+      b = TYPE_PRECISION (TREE_TYPE (ranges[i].exp)) * 2 + !zero_p;
+      if (buckets.length () <= b)
+	buckets.safe_grow_cleared (b + 1);
+      if (chains.length () <= (unsigned) i)
+	chains.safe_grow (i + 1);
+      chains[i] = buckets[b];
+      buckets[b] = i + 1;
+    }
+
+  FOR_EACH_VEC_ELT (buckets, b, i)
+    if (i && chains[i - 1])
+      {
+	int j, k = i;
+	for (j = chains[i - 1]; j; j = chains[j - 1])
+	  {
+	    gimple *gk = SSA_NAME_DEF_STMT (ranges[k - 1].exp);
+	    gimple *gj = SSA_NAME_DEF_STMT (ranges[j - 1].exp);
+	    if (reassoc_stmt_dominates_stmt_p (gk, gj))
+	      k = j;
+	  }
+	tree type1 = TREE_TYPE (ranges[k - 1].exp);
+	tree type2 = NULL_TREE;
+	bool strict_overflow_p = false;
+	candidates.truncate (0);
+	for (j = i; j; j = chains[j - 1])
+	  {
+	    tree type = TREE_TYPE (ranges[j - 1].exp);
+	    strict_overflow_p |= ranges[j - 1].strict_overflow_p;
+	    if (j == k
+		|| useless_type_conversion_p (type1, type))
+	      ;
+	    else if (type2 == NULL_TREE
+		     || useless_type_conversion_p (type2, type))
+	      {
+		if (type2 == NULL_TREE)
+		  type2 = type;
+		candidates.safe_push (&ranges[j - 1]);
+	      }
+	  }
+	unsigned l = candidates.length ();
+	for (j = i; j; j = chains[j - 1])
+	  {
+	    tree type = TREE_TYPE (ranges[j - 1].exp);
+	    if (j == k)
+	      continue;
+	    if (useless_type_conversion_p (type1, type))
+	      ;
+	    else if (type2 == NULL_TREE
+		     || useless_type_conversion_p (type2, type))
+	      continue;
+	    candidates.safe_push (&ranges[j - 1]);
+	  }
+	gimple_seq seq = NULL;
+	tree op = NULL_TREE;
+	unsigned int id;
+	struct range_entry *r;
+	candidates.safe_push (&ranges[k - 1]);
+	FOR_EACH_VEC_ELT (candidates, id, r)
+	  {
+	    gimple *g;
+	    if (id == 0)
+	      {
+		op = r->exp;
+		continue;
+	      }
+	    if (id == l)
+	      {
+		g = gimple_build_assign (make_ssa_name (type1), NOP_EXPR, op);
+		gimple_seq_add_stmt_without_update (&seq, g);
+		op = gimple_assign_lhs (g);
+	      }
+	    tree type = TREE_TYPE (r->exp);
+	    tree exp = r->exp;
+	    if (id >= l && !useless_type_conversion_p (type1, type))
+	      {
+		g = gimple_build_assign (make_ssa_name (type1), NOP_EXPR, exp);
+		gimple_seq_add_stmt_without_update (&seq, g);
+		exp = gimple_assign_lhs (g);
+	      }
+	    g = gimple_build_assign (make_ssa_name (id >= l ? type1 : type2),
+				     (b & 1) ? BIT_AND_EXPR : BIT_IOR_EXPR,
+				     op, exp);
+	    gimple_seq_add_stmt_without_update (&seq, g);
+	    op = gimple_assign_lhs (g);
+	  }
+	candidates.pop ();
+	if (update_range_test (&ranges[k - 1], NULL, candidates.address (),
+			       candidates.length (), opcode, ops, op,
+			       seq, true, ranges[k - 1].low,
+			       ranges[k - 1].low, strict_overflow_p))
+	  any_changes = true;
+	else
+	  gimple_seq_discard (seq);
+      }
+
+  return any_changes;
+}
+
 /* Attempt to optimize for signed a and b where b is known to be >= 0:
    a >= 0 && a < b into (unsigned) a < (unsigned) b
    a >= 0 && a <= b into (unsigned) a <= (unsigned) b  */
@@ -3202,6 +3339,8 @@ optimize_range_tests (enum tree_code opc
   if (lshift_cheap_p (optimize_function_for_speed_p (cfun)))
     any_changes |= optimize_range_tests_to_bit_test (opcode, first, length,
 						     ops, ranges);
+  any_changes |= optimize_range_tests_cmp_bitwise (opcode, first, length,
+						   ops, ranges);
   any_changes |= optimize_range_tests_var_bound (opcode, first, length, ops,
 						 ranges);
 
--- gcc/testsuite/gcc.dg/pr35691-5.c.jj	2017-09-26 10:47:38.507599980 +0200
+++ gcc/testsuite/gcc.dg/pr35691-5.c	2017-09-26 11:33:06.000000000 +0200
@@ -0,0 +1,125 @@
+/* PR middle-end/35691 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xyz]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[ghi]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[ghi]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[ghi]1_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f1 (int x1, unsigned int y1, int z1, _Bool d, _Bool e, _Bool f, long long g1, unsigned long long h1, long long i1)
+{
+  int a = x1 == 0;
+  int b = y1 == 0;
+  int c = z1 == 0;
+  int j = g1 == 0;
+  int k = h1 == 0;
+  int l = i1 == 0;
+  return a && d && j && b && e && l && f && c && k;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xyz]2_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]2_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]2_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[ghi]2_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[ghi]2_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[ghi]2_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f2 (int x2, int y2, unsigned int z2, _Bool d, _Bool e, _Bool f, long long g2, unsigned long long h2, long long i2)
+{
+  int a = x2 == 0;
+  int b = y2 == 0;
+  int c = z2 == 0;
+  int j = g2 == -1LL;
+  int k = h2 == -1ULL;
+  int l = i2 == -1LL;
+  return !a || d || !l || !b || !k || e || f || !c || !j;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xyz]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[xyz]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[xyz]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[ghi]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[ghi]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[ghi]3_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f3 (unsigned int x3, int y3, int z3, _Bool d, _Bool e, _Bool f, signed char g3, unsigned char h3, signed char i3)
+{
+  int a = x3 == -1U;
+  int b = y3 == -1;
+  int c = z3 == -1;
+  int j = g3 == -1;
+  int k = h3 == (unsigned char) -1U;
+  int l = i3 == -1;
+  return a && d && j && b && k && e && f && c && l;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xyz]4_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[xyz]4_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[xyz]4_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f4 (int x4, unsigned int y4, unsigned int z4, _Bool d, _Bool e, _Bool f)
+{
+  int a = x4 == -1U;
+  int b = y4 == -1U;
+  int c = z4 == -1;
+  return !a || d || !b || e || f || !c;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xyz]5_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]5_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]5_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f5 (int x5, int y5, int z5, _Bool d, _Bool e, _Bool f)
+{
+  int a = x5 == 0;
+  int b = y5 != 0;
+  int c = z5 != 0;
+  return a && d && !b && e && f && !c;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xyz]6_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]6_\[0-9]*\\(D\\) \\+\\\[0, 0\\\] and \[xyz]6_\[0-9]*\\(D\\) \\+\\\[0, 0\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f6 (unsigned int x6, unsigned int y6, unsigned int z6, _Bool d, _Bool e, _Bool f)
+{
+  int a = x6 == 0;
+  int b = y6 != 0;
+  int c = z6 != 0;
+  return !a || d || b || e || f || c;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xy]7_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[xy]7_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f7 (int x7, int y7, int z7, _Bool d, _Bool e, _Bool f)
+{
+  int a = x7 == -1;
+  int b = y7 != -1;
+  int c = z7 == -1;
+  return a && d && !b && e && f && !c;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[xy]8_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\] and \[xy]8_\[0-9]*\\(D\\) \\+\\\[\[1-9-]\[0-9]*, \[1-9-]\[0-9]*\\\]\[\n\r]" 1 "reassoc1" } } */
+
+int
+f8 (unsigned int x8, unsigned int y8, unsigned int z8, _Bool d, _Bool e, _Bool f)
+{
+  int a = x8 == -1;
+  int b = y8 != -1;
+  int c = z8 == -1;
+  return !a || d || b || e || f || c;
+}
+
+/* { dg-final { scan-tree-dump-not "Optimizing range tests \[xyz]9_\[0-9]*\\(D\\)" "reassoc1" } } */
+
+int
+f9 (int x9, int y9, int z9, _Bool d, _Bool e, _Bool f)
+{
+  int a = x9 == -1;
+  int b = y9 == -1;
+  int c = z9 == -1;
+  return a || d || b || e || f || c;
+}
+
+/* { dg-final { scan-tree-dump-not "Optimizing range tests \[xyz]0_\[0-9]*\\(D\\)" "reassoc1" } } */
+
+int
+f0 (int x0, int y0, int z0, _Bool d, _Bool e, _Bool f)
+{
+  int a = x0 != 0;
+  int b = y0 != 0;
+  int c = z0 != 0;
+  return a && d && b && e && f && c;
+}
--- gcc/testsuite/gcc.dg/pr35691-6.c.jj	2017-09-26 11:26:32.129418103 +0200
+++ gcc/testsuite/gcc.dg/pr35691-6.c	2017-09-26 11:25:59.000000000 +0200
@@ -0,0 +1,72 @@
+/* PR middle-end/35691 */
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+__attribute__((noinline, noclone)) int
+foo (int *p, unsigned long long *q)
+{
+  int p0 = p[0], p10 = p[10], p12 = p[12], p32 = p[32], p77 = p[77], p85 = p[85], p86 = p[86], p97 = p[97], p98 = p[98];
+  unsigned long long q0 = q[0], q10 = q[10], q12 = q[12], q32 = q[32], q77 = q[77], q85 = q[85], q86 = q[86], q97 = q[97], q98 = q[98];
+  return p0 == 0 && q0 == -1 && p10 == 0 && q10 == -1 && p12 == 0 && q12 == -1
+	 && p32 == 0 && q32 == -1 && p77 == 0 && q77 == -1 && p85 == 0 && q85 == -1
+	 && p86 == 0 && q86 == -1 && p97 == 0 && q97 == -1 && p98 == 0 && q98 == -1;
+}
+
+__attribute__((noinline, noclone)) int
+bar (int *p, unsigned long long *q)
+{
+  int p0 = p[0], p10 = p[10], p12 = p[12], p32 = p[32], p77 = p[77], p85 = p[85], p86 = p[86], p97 = p[97], p98 = p[98];
+  unsigned long long q0 = q[0], q10 = q[10], q12 = q[12], q32 = q[32], q77 = q[77], q85 = q[85], q86 = q[86], q97 = q[97], q98 = q[98];
+  return p0 != 0 | q0 != -1 | p10 != 0 | q10 != -1 | p12 != 0 | q12 != -1
+	 | p32 != 0 | q32 != -1 | p77 != 0 | q77 != -1 | p85 != 0 | q85 != -1
+	 | p86 != 0 | q86 != -1 | p97 != 0 | q97 != -1 | p98 != 0 | q98 != -1;
+}
+
+int p[100];
+unsigned long long q[100];
+
+int
+main ()
+{
+  int i;
+  for (i = 0; i < 100; i++)
+    {
+      p[i] = 0;
+      q[i] = -1;
+    }
+  asm volatile ("" : : "g" (p), "g" (q) : "memory");
+  if (foo (p, q) != 1 || bar (p, q) != 0)
+    __builtin_abort ();
+  for (i = 0; i < 100; i++)
+    {
+      int f1, b1, f2, b2;
+      p[i] = 1;
+      f1 = foo (p, q);
+      b1 = bar (p, q);
+      p[i] = 0;
+      q[i] = 0;
+      f2 = foo (p, q);
+      b2 = bar (p, q);
+      q[i] = -1;
+      switch (i)
+	{
+	case 0:
+	case 10:
+	case 12:
+	case 32:
+	case 77:
+	case 85:
+	case 86:
+	case 97:
+	case 98:
+	  if (f1 != 0 || b1 != 1 || f2 != 0 || b2 != 1)
+	    __builtin_abort ();
+	  break;
+	default:
+	  if (f1 != 1 || b1 != 0 || f2 != 1 || b2 != 0)
+	    __builtin_abort ();
+	  break;
+	}
+    }
+  return 0;
+}

	Jakub