Fix PR 110874: infinite loop in gimple_bitwise_inverted_equal_p with fre

This changes gimple_bitwise_inverted_equal_p to use a 2 different match patterns
to try to match bit_not wrapped with a possible nop_convert and a comparison
also wrapped with a possible nop_convert. This is to avoid being recursive.

OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.

gcc/ChangeLog:

	PR tree-optimization/110874
	* gimple-match-head.cc (gimple_bit_not_with_nop): New declaration.
	(gimple_maybe_cmp): Likewise.
	(gimple_bitwise_inverted_equal_p): Rewrite to use gimple_bit_not_with_nop
	and gimple_maybe_cmp instead of being recursive.
	* match.pd (bit_not_with_nop): New match pattern.
	(maybe_cmp): Likewise.

gcc/testsuite/ChangeLog:

	PR tree-optimization/110874
	* gcc.c-torture/compile/pr110874-a.c: New test.

3 files changed, 79 insertions, 42 deletions

diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc
index b1e9630..a097a49 100644
--- a/gcc/gimple-match-head.cc
+++ b/gcc/gimple-match-head.cc
@@ -270,6 +270,10 @@ gimple_bitwise_equal_p (tree expr1, tree expr2, tree (*valueize) (tree))
 #define bitwise_inverted_equal_p(expr1, expr2) \
   gimple_bitwise_inverted_equal_p (expr1, expr2, valueize)
 
+
+bool gimple_bit_not_with_nop (tree, tree *, tree (*) (tree));
+bool gimple_maybe_cmp (tree, tree *, tree (*) (tree));
+
 /* Helper function for bitwise_equal_p macro.  */
 
 static inline bool
@@ -285,52 +289,51 @@ gimple_bitwise_inverted_equal_p (tree expr1, tree expr2, tree (*valueize) (tree)
     return false;
 
   tree other;
-  if (gimple_nop_convert (expr1, &other, valueize)
-      && gimple_bitwise_inverted_equal_p (other, expr2, valueize))
-    return true;
-
-  if (gimple_nop_convert (expr2, &other, valueize)
-      && gimple_bitwise_inverted_equal_p (expr1, other, valueize))
-    return true;
-
-  if (TREE_CODE (expr1) != SSA_NAME
-      || TREE_CODE (expr2) != SSA_NAME)
-    return false;
-
-  gimple *d1 = get_def (valueize, expr1);
-  gassign *a1 = safe_dyn_cast <gassign *> (d1);
-  gimple *d2 = get_def (valueize, expr2);
-  gassign *a2 = safe_dyn_cast <gassign *> (d2);
-  if (a1
-      && gimple_assign_rhs_code (a1) == BIT_NOT_EXPR
-      && gimple_bitwise_equal_p (do_valueize (valueize,
-					      gimple_assign_rhs1 (a1)),
-				 expr2, valueize))
+  /* Try if EXPR1 was defined as ~EXPR2. */
+  if (gimple_bit_not_with_nop (expr1, &other, valueize))
+    {
+      if (operand_equal_p (other, expr2, 0))
 	return true;
-  if (a2
-      && gimple_assign_rhs_code (a2) == BIT_NOT_EXPR
-      && gimple_bitwise_equal_p (expr1,
-				 do_valueize (valueize,
-					      gimple_assign_rhs1 (a2)),
-				 valueize))
+      tree expr4;
+      if (gimple_nop_convert (expr2, &expr4, valueize)
+	  && operand_equal_p (other, expr4, 0))
 	return true;
-
-  if (a1 && a2
-      && TREE_CODE_CLASS (gimple_assign_rhs_code (a1)) == tcc_comparison
-      && TREE_CODE_CLASS (gimple_assign_rhs_code (a2)) == tcc_comparison)
+    }
+  /* Try if EXPR2 was defined as ~EXPR1. */
+  if (gimple_bit_not_with_nop (expr2, &other, valueize))
     {
-      tree op10 = do_valueize (valueize, gimple_assign_rhs1 (a1));
-      tree op20 = do_valueize (valueize, gimple_assign_rhs1 (a2));
-      if (!operand_equal_p (op10, op20))
-        return false;
-      tree op11 = do_valueize (valueize, gimple_assign_rhs2 (a1));
-      tree op21 = do_valueize (valueize, gimple_assign_rhs2 (a2));
-      if (!operand_equal_p (op11, op21))
-        return false;
-      if (invert_tree_comparison (gimple_assign_rhs_code (a1),
-				  HONOR_NANS (op10))
-	  == gimple_assign_rhs_code (a2))
+      if (operand_equal_p (other, expr1, 0))
+	return true;
+      tree expr3;
+      if (gimple_nop_convert (expr1, &expr3, valueize)
+	  && operand_equal_p (other, expr3, 0))
 	return true;
     }
+
+  /* If neither are defined by BIT_NOT, try to see if
+     both are defined by comparisons and see if they are
+     complementary (inversion) of each other. */
+  tree newexpr1, newexpr2;
+  if (!gimple_maybe_cmp (expr1, &newexpr1, valueize))
+    return false;
+  if (!gimple_maybe_cmp (expr2, &newexpr2, valueize))
+    return false;
+
+  gimple *d1 = get_def (valueize, newexpr1);
+  gassign *a1 = dyn_cast <gassign *> (d1);
+  gimple *d2 = get_def (valueize, newexpr2);
+  gassign *a2 = dyn_cast <gassign *> (d2);
+  tree op10 = do_valueize (valueize, gimple_assign_rhs1 (a1));
+  tree op20 = do_valueize (valueize, gimple_assign_rhs1 (a2));
+  if (!operand_equal_p (op10, op20))
+    return false;
+  tree op11 = do_valueize (valueize, gimple_assign_rhs2 (a1));
+  tree op21 = do_valueize (valueize, gimple_assign_rhs2 (a2));
+  if (!operand_equal_p (op11, op21))
+    return false;
+  if (invert_tree_comparison (gimple_assign_rhs_code (a1),
+			      HONOR_NANS (op10))
+	== gimple_assign_rhs_code (a2))
+    return true;
   return false;
 }
diff --git a/gcc/match.pd b/gcc/match.pd
index a978dc5..aa49574 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -155,6 +155,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
 		   TYPE_VECTOR_SUBPARTS (TREE_TYPE (@0)))
       && tree_nop_conversion_p (TREE_TYPE (type), TREE_TYPE (TREE_TYPE (@0))))))
 
+#if GIMPLE
+/* These are used by gimple_bitwise_inverted_equal_p to simplify
+   detection of BIT_NOT and comparisons. */
+(match (bit_not_with_nop @0)
+ (bit_not @0))
+(match (bit_not_with_nop @0)
+ (convert (bit_not @0))
+ (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))))
+(for cmp (tcc_comparison)
+ (match (maybe_cmp @0)
+  (cmp@0 @1 @2))
+ (match (maybe_cmp @0)
+  (convert (cmp@0 @1 @2))
+   (if (tree_nop_conversion_p (type, TREE_TYPE (@0)))))
+)
+#endif
+
 /* Transform likes of (char) ABS_EXPR <(int) x> into (char) ABSU_EXPR <x>
    ABSU_EXPR returns unsigned absolute value of the operand and the operand
    of the ABSU_EXPR will have the corresponding signed type.  */
diff --git a/gcc/testsuite/gcc.c-torture/compile/pr110874-a.c b/gcc/testsuite/gcc.c-torture/compile/pr110874-a.c
new file mode 100644
index 0000000..b314410
--- /dev/null
+++ b/gcc/testsuite/gcc.c-torture/compile/pr110874-a.c
@@ -0,0 +1,17 @@
+struct S1 {
+  unsigned f0;
+};
+static int g_161;
+void func_109(unsigned g_227, unsigned t) {
+  struct S1 l_178;
+  int l_160 = 0x1FAE99D5L;
+  int *l_230[] = {&l_160};
+  if (l_160) {
+    for (l_178.f0 = -7; l_178.f0;) {
+      ++g_227;
+      break;
+    }
+    (g_161) = g_227;
+  }
+  (g_161) &= t;
+}