Fix isShiftedInt and isShiftedUint for widths > 32.

[jlebar]

Summary

Previously we were doing 1 << S. "1" is an int, so this doesn't work
when S >= 32.

This patch also adds some static_asserts to these functions to ensure
that we don't hit UB by shifting left too much.

[RKSimon]

This has introduced a compile warning on VS2015 builds:

1> MathExtrasTest.cpp
1> .\llvm\include\llvm/Support/MathExtras.h(296): warning C4293: '<<': shift count negative or too big, undefined behavior
1> .\llvm\include\llvm/Support/MathExtras.h(322): note: see reference to function template instantiation 'bool llvm::isUInt<64>(uint64_t)' being compiled
1> .\llvm\unittests\Support\MathExtrasTest.cpp(401): note: see reference to function template instantiation 'bool llvm::isShiftedUInt<1,63>(uint64_t)' being compiled

[jlebar]

1> .\llvm\include\llvm/Support/MathExtras.h(296): warning C4293: '<<': shift count negative or too big, undefined behavior
1> .\llvm\include\llvm/Support/MathExtras.h(322): note: see reference to function template instantiation 'bool llvm::isUInt<64>(uint64_t)' being compiled
1> .\llvm\unittests\Support\MathExtrasTest.cpp(401): note: see reference to function template instantiation 'bool llvm::isShiftedUInt<1,63>(uint64_t)' being compiled

Ugh. I think MSVC is wrong. isUInt<64> does

return N >= 64 || x < (UINT64_C(1)<<(N));

Which should be safe because of short-circuit evaluation.

I guess we can specialize the isUInt<N> template. :-/ Can we file a bug on msvc?

[jlebar]

RKSimon, can you try D22472? I'm going to close this revision again, otherwise it's confusing to have an open revision after the patch has landed. Let's take further discussion into that thread, if that's OK.

[RKSimon]

In D22441#487373, @jlebar wrote:

RKSimon, can you try D22472? I'm going to close this revision again, otherwise it's confusing to have an open revision after the patch has landed. Let's take further discussion into that thread, if that's OK.

Thanks its fixed the shift count warning but now has an operator precedence warning.

If you're after a buildbot to check things, llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast will help. It doesn't treat warnings as errors so the build stays green and you need to drill down into the build stdio:

http://lab.llvm.org:8011/builders/llvm-clang-lld-x86_64-scei-ps4-windows10pro-fast/builds/8507/steps/build/logs/warnings%20%283%29

[RKSimon]

In D22441#487625, @RKSimon wrote:

In D22441#487373, @jlebar wrote:

RKSimon, can you try D22472? I'm going to close this revision again, otherwise it's confusing to have an open revision after the patch has landed. Let's take further discussion into that thread, if that's OK.

Thanks its fixed the shift count warning but now has an operator precedence warning.

This is fixed in rL275971

include/llvm/Support/MathExtras.h

 inline bool isInt<32>(int64_t x) {
   return static_cast<int32_t>(x) == x;
 }
 
 /// isShiftedInt<N,S> - Checks if a signed integer is an N bit number shifted
 ///                     left by S.
 template<unsigned N, unsigned S>
 inline bool isShiftedInt(int64_t x) {
-  return isInt<N+S>(x) && (x % (1<<S) == 0);
+  static_assert(
+      N > 0, "isShiftedInt<0> doesn't make sense (refers to a 0-bit number.");
+  static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide.");
+  return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
 }
 
 /// isUInt - Checks if an unsigned integer fits into the given bit width.
 template<unsigned N>
 inline bool isUInt(uint64_t x) {
+  static_assert(N > 0, "isUInt<0> doesn't make sense.");
   return N >= 64 || x < (UINT64_C(1)<<(N));
 }
 // Template specializations to get better code for common cases.
 template<>
 inline bool isUInt<8>(uint64_t x) {
   return static_cast<uint8_t>(x) == x;
 }
 template<>
 inline bool isUInt<16>(uint64_t x) {
   return static_cast<uint16_t>(x) == x;
 }
 template<>
 inline bool isUInt<32>(uint64_t x) {
   return static_cast<uint32_t>(x) == x;
 }
 
-/// isShiftedUInt<N,S> - Checks if a unsigned integer is an N bit number shifted
-///                     left by S.
+/// Checks if a unsigned integer is an N bit number shifted left by S.
 template<unsigned N, unsigned S>
 inline bool isShiftedUInt(uint64_t x) {
-  return isUInt<N+S>(x) && (x % (1<<S) == 0);
+  static_assert(
+      N > 0, "isShiftedUInt<0> doesn't make sense (refers to a 0-bit number)");
+  static_assert(N + S <= 64,
+                "isShiftedUInt<N, S> with N + S > 64 is too wide.");
+  // Per the two static_asserts above, S must be strictly less than 64.  So
+  // 1 << S is not undefined behavior.
+  return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0);
 }
 
 /// Gets the maximum value for a N-bit unsigned integer.
 inline uint64_t maxUIntN(uint64_t N) {
   assert(N > 0 && N <= 64 && "integer width out of range");
 
   // uint64_t(1) << 64 is undefined behavior, so we can't do
   //   (uint64_t(1) << N) - 1

unittests/Support/MathExtrasTest.cpp

 
 TEST(MathExtras, SaturatingMultiplyAdd) {
   SaturatingMultiplyAddTestHelper<uint8_t>();
   SaturatingMultiplyAddTestHelper<uint16_t>();
   SaturatingMultiplyAddTestHelper<uint32_t>();
   SaturatingMultiplyAddTestHelper<uint64_t>();
 }
 
+TEST(MathExtras, IsShiftedUInt) {
+  EXPECT_TRUE((isShiftedUInt<1, 0>(0)));
+  EXPECT_TRUE((isShiftedUInt<1, 0>(1)));
+  EXPECT_FALSE((isShiftedUInt<1, 0>(2)));
+  EXPECT_FALSE((isShiftedUInt<1, 0>(3)));
+  EXPECT_FALSE((isShiftedUInt<1, 0>(0x8000000000000000)));
+  EXPECT_TRUE((isShiftedUInt<1, 63>(0x8000000000000000)));
+  EXPECT_TRUE((isShiftedUInt<2, 62>(0xC000000000000000)));
+  EXPECT_FALSE((isShiftedUInt<2, 62>(0xE000000000000000)));
+
+  // 0x201 is ten bits long and has a 1 in the MSB and LSB.
+  EXPECT_TRUE((isShiftedUInt<10, 5>(uint64_t(0x201) << 5)));
+  EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 4)));
+  EXPECT_FALSE((isShiftedUInt<10, 5>(uint64_t(0x201) << 6)));
+}
+
+TEST(MathExtras, IsShiftedInt) {
+  EXPECT_TRUE((isShiftedInt<1, 0>(0)));
+  EXPECT_TRUE((isShiftedInt<1, 0>(-1)));
+  EXPECT_FALSE((isShiftedInt<1, 0>(2)));
+  EXPECT_FALSE((isShiftedInt<1, 0>(3)));
+  EXPECT_FALSE((isShiftedInt<1, 0>(0x8000000000000000)));
+  EXPECT_TRUE((isShiftedInt<1, 63>(0x8000000000000000)));
+  EXPECT_TRUE((isShiftedInt<2, 62>(0xC000000000000000)));
+  EXPECT_FALSE((isShiftedInt<2, 62>(0xE000000000000000)));
+
+  // 0x201 is ten bits long and has a 1 in the MSB and LSB.
+  EXPECT_TRUE((isShiftedInt<11, 5>(int64_t(0x201) << 5)));
+  EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 3)));
+  EXPECT_FALSE((isShiftedInt<11, 5>(int64_t(0x201) << 6)));
+  EXPECT_TRUE((isShiftedInt<11, 5>(-(int64_t(0x201) << 5))));
+  EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 3))));
+  EXPECT_FALSE((isShiftedInt<11, 5>(-(int64_t(0x201) << 6))));
+
+  EXPECT_TRUE((isShiftedInt<6, 10>(-(int64_t(1) << 15))));
+  EXPECT_FALSE((isShiftedInt<6, 10>(int64_t(1) << 15)));
 }