From 001121e8921d5d1a439ce0e64ab04c5959b0bfd8 Mon Sep 17 00:00:00 2001 From: Jakub Jelinek Date: Tue, 17 Jan 2023 12:14:25 +0100 Subject: 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 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. --- gcc/testsuite/c-c++-common/rotate-2.c | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) (limited to 'gcc/testsuite/c-c++-common/rotate-2.c') 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))); } -- cgit v1.1