From d2eb616a0f7bea78164912aa438c29fe1ef5774a Mon Sep 17 00:00:00 2001
From: Jakub Jelinek <jakub@redhat.com>
Date: Thu, 31 Dec 2020 11:09:26 +0100
Subject: [PATCH] match.pd: Add clz(X) == 0 -> (int)X < 0 etc. simpifications
 [PR94802]

The following patch adds some clz simplifications.  If
clz is 0, then the MSB of the argument is set, and if clz is prec-1, then
the argument is 1.

2020-12-31  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/94802
	* match.pd (clz(X) == 0 -> (int)X < 0): New simplification.
	(clz(X) == (prec-1) -> X == 1): Likewise.

	* gcc.dg/tree-ssa/pr94802-1.c: New test.
---
 gcc/match.pd                              | 33 +++++++++++
 gcc/testsuite/gcc.dg/tree-ssa/pr94802-1.c | 68 +++++++++++++++++++++++
 2 files changed, 101 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr94802-1.c

diff --git a/gcc/match.pd b/gcc/match.pd
index 1055292d2e9..529933f978b 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -6226,6 +6226,39 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
   (if (single_use (@3))
    (IFN_FMA @0 @1 @2))))
 
+/* CLZ simplifications.  */
+(for clz (CLZ)
+ (for op (eq ne)
+      cmp (lt ge)
+  (simplify
+   (op (clz:s @0) INTEGER_CST@1)
+   (if (integer_zerop (@1))
+    /* clz(X) == 0 is (int)X < 0 and clz(X) != 0 is (int)X >= 0.  */
+    (with { tree stype = signed_type_for (TREE_TYPE (@0));
+	    HOST_WIDE_INT val = 0;
+#ifdef CLZ_DEFINED_VALUE_AT_ZERO
+	    /* Punt on hypothetical weird targets.  */
+	    if (CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@0)),
+					   val) == 2
+		&& val == 0)
+	      stype = NULL_TREE;
+#endif
+	  }
+     (if (stype)
+      (cmp (convert:stype @0) { build_zero_cst (stype); })))
+    /* clz(X) == (prec-1) is X == 1 and clz(X) != (prec-1) is X != 1.  */
+    (with { bool ok = true;
+#ifdef CLZ_DEFINED_VALUE_AT_ZERO
+	    /* Punt on hypothetical weird targets.  */
+	    if (CLZ_DEFINED_VALUE_AT_ZERO (TYPE_MODE (TREE_TYPE (@0)),
+					   val) == 2
+		&& val == TYPE_PRECISION (TREE_TYPE (@0)) - 1)
+	      ok = false;
+#endif
+	  }
+     (if (ok && wi::to_wide (@1) == (TYPE_PRECISION (TREE_TYPE (@0)) - 1))
+      (op @0 { build_one_cst (TREE_TYPE (@0)); })))))))
+
 /* POPCOUNT simplifications.  */
 /* popcount(X) + popcount(Y) is popcount(X|Y) when X&Y must be zero.  */
 (simplify
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr94802-1.c b/gcc/testsuite/gcc.dg/tree-ssa/pr94802-1.c
new file mode 100644
index 00000000000..8175704f40c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr94802-1.c
@@ -0,0 +1,68 @@
+/* PR tree-optimization/94802 */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* { dg-final { scan-tree-dump-not " = __builtin_clz " "optimized" } } */
+
+__attribute__((noipa)) int
+f1 (int a, int b)
+{
+  return __builtin_clz (a - b) != 0;
+}
+
+__attribute__((noipa)) int
+f2 (int x)
+{
+  return __builtin_clz (x) == 0;
+}
+
+__attribute__((noipa)) int
+f3 (int x)
+{
+  return __builtin_clz (x) != 0;
+}
+
+__attribute__((noipa)) int
+f4 (int a, int b)
+{
+  return __builtin_clz (a - b) == sizeof (int) * __CHAR_BIT__ - 1;
+}
+
+__attribute__((noipa)) int
+f5 (int x)
+{
+  return __builtin_clz (x) == sizeof (int) * __CHAR_BIT__ - 1;
+}
+
+__attribute__((noipa)) int
+f6 (int x)
+{
+  return __builtin_clz (x) != sizeof (int) * __CHAR_BIT__ - 1;
+}
+
+int
+main ()
+{
+  if (f1 (5, 7) != 0
+      || f1 (7, 5) != 1
+      || f2 (1) != 0
+      || f2 (137) != 0
+      || f2 (-1) != 1
+      || f2 (-137) != 1
+      || f3 (1) != 1
+      || f3 (137) != 1
+      || f3 (-1) != 0
+      || f3 (-137) != 0
+      || f4 (5, 4) != 1
+      || f4 (6, 4) != 0
+      || f4 (4, 5) != 0
+      || f5 (1) != 1
+      || f5 (17) != 0
+      || f5 (-1) != 0
+      || f5 (-17) != 0
+      || f6 (1) != 0
+      || f6 (17) != 1
+      || f6 (-1) != 1
+      || f6 (-17) != 1)
+    __builtin_abort ();
+  return 0;
+}
-- 
2.30.2