forwprop: Fix up rotate pattern matching [PR106523]

The comment above simplify_rotate roughly describes what patterns
are matched into what:
   We are looking for X with unsigned type T with bitsize B, OP being
   +, | or ^, some type T2 wider than T.  For:
   (X << CNT1) OP (X >> CNT2)                           iff CNT1 + CNT2 == B
   ((T) ((T2) X << CNT1)) OP ((T) ((T2) X >> CNT2))     iff CNT1 + CNT2 == B

   transform these into:
   X r<< CNT1

   Or for:
   (X << Y) OP (X >> (B - Y))
   (X << (int) Y) OP (X >> (int) (B - Y))
   ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
   ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
   (X << Y) | (X >> ((-Y) & (B - 1)))
   (X << (int) Y) | (X >> (int) ((-Y) & (B - 1)))
   ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
   ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))

   transform these into (last 2 only if ranger can prove Y < B):
   X r<< Y

   Or for:
   (X << (Y & (B - 1))) | (X >> ((-Y) & (B - 1)))
   (X << (int) (Y & (B - 1))) | (X >> (int) ((-Y) & (B - 1)))
   ((T) ((T2) X << (Y & (B - 1)))) | ((T) ((T2) X >> ((-Y) & (B - 1))))
   ((T) ((T2) X << (int) (Y & (B - 1)))) \
     | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))

   transform these into:
   X r<< (Y & (B - 1))

The following testcase shows that 2 of these are problematic.
If T2 is wider than T, then the 2 which yse (-Y) & (B - 1) on one
of the shift counts but Y on the can do something different from
rotate.  E.g.:
__attribute__((noipa)) unsigned char
f7 (unsigned char x, unsigned int y)
{
  unsigned int t = x;
  return (t << y) | (t >> ((-y) & 7));
}
if y is [0, 7], then it is a normal rotate, and if y is in [32, ~0U]
then it is UB, but for y in [9, 31] the left shift in this case
will never leave any bits in the result, while in a rotate they are
left there.  Say for y 5 and x 0xaa the expression gives
0x55 which is the same thing as rotate, while for y 19 and x 0xaa
0x5, which is different.
Now, I believe the
   ((T) ((T2) X << Y)) OP ((T) ((T2) X >> (B - Y)))
   ((T) ((T2) X << (int) Y)) OP ((T) ((T2) X >> (int) (B - Y)))
forms are ok, because B - Y still needs to be a valid shift count,
and if Y > B then B - Y should be either negative or very large
positive (for unsigned types).
And similarly the last 2 cases above which use & (B - 1) on both
shift operands are definitely ok.

The following patch disables the
   ((T) ((T2) X << Y)) | ((T) ((T2) X >> ((-Y) & (B - 1))))
   ((T) ((T2) X << (int) Y)) | ((T) ((T2) X >> (int) ((-Y) & (B - 1))))
unless ranger says Y is not in [B, B2 - 1] range.

And, looking at it again this morning, actually the Y equal to B
case is still fine, if Y is equal to 0, then it is
(T) (((T2) X << 0) | ((T2) X >> 0))
and so X, for Y == B it is
(T) (((T2) X << B) | ((T2) X >> 0))
which is the same as
(T) (0 | ((T2) X >> 0))
which is also X.  So instead of the [B, B2 - 1] range we could use
[B + 1, B2 - 1].  And, if we wanted to go further, even multiplies
of B are ok if they are smaller than B2, so we could construct a detailed
int_range_max if we wanted.

2023-01-17  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/106523
	* tree-ssa-forwprop.cc (simplify_rotate): For the
	patterns with (-Y) & (B - 1) in one operand's shift
	count and Y in another, if T2 has wider precision than T,
	punt if Y could have a value in [B, B2 - 1] range.

	* c-c++-common/rotate-2.c (f5, f6, f7, f8, f13, f14, f15, f16,
	f37, f38, f39, f40, f45, f46, f47, f48): Add assertions using
	__builtin_unreachable about shift count.
	* c-c++-common/rotate-2b.c: New test.
	* c-c++-common/rotate-4.c (f5, f6, f7, f8, f13, f14, f15, f16,
	f37, f38, f39, f40, f45, f46, f47, f48): Add assertions using
	__builtin_unreachable about shift count.
	* c-c++-common/rotate-4b.c: New test.
	* gcc.c-torture/execute/pr106523.c: New test.

1 files changed, 32 insertions, 0 deletions

diff --git a/gcc/testsuite/c-c++-common/rotate-2.c b/gcc/testsuite/c-c++-common/rotate-2.c
index c8359cd..544a7ca 100644
--- a/gcc/testsuite/c-c++-common/rotate-2.c
+++ b/gcc/testsuite/c-c++-common/rotate-2.c
@@ -32,24 +32,32 @@ f4 (unsigned int x, int y __attribute__((unused)))
 unsigned short int
 f5 (unsigned short int x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
 }
 
 unsigned short int
 f6 (unsigned short int x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
 }
 
 unsigned char
 f7 (unsigned char x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ - 1)));
 }
 
 unsigned char
 f8 (unsigned char x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ - 1)));
 }
 
@@ -80,24 +88,32 @@ f12 (unsigned int x, int y __attribute__((unused)))
 unsigned short int
 f13 (unsigned short int x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
 }
 
 unsigned short int
 f14 (unsigned short int x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
 }
 
 unsigned char
 f15 (unsigned char x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
 }
 
 unsigned char
 f16 (unsigned char x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x << y) | (x >> ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
 }
 
@@ -224,24 +240,32 @@ f36 (unsigned int x, int y __attribute__((unused)))
 unsigned short int
 f37 (unsigned short int x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
 }
 
 unsigned short int
 f38 (unsigned short int x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ * __SIZEOF_SHORT__ - 1)));
 }
 
 unsigned char
 f39 (unsigned char x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ - 1)));
 }
 
 unsigned char
 f40 (unsigned char x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ - 1)));
 }
 
@@ -272,24 +296,32 @@ f44 (unsigned int x, int y __attribute__((unused)))
 unsigned short int
 f45 (unsigned short int x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
 }
 
 unsigned short int
 f46 (unsigned short int x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__ * __SIZEOF_SHORT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned short) - 1)));
 }
 
 unsigned char
 f47 (unsigned char x, unsigned int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
 }
 
 unsigned char
 f48 (unsigned char x, unsigned long int y)
 {
+  if (y >= __CHAR_BIT__)
+    __builtin_unreachable ();
   return (x >> y) | (x << ((-y) & (__CHAR_BIT__ * sizeof (unsigned char) - 1)));
 }