Use a faster implementation of maxUIntN.

[jlebar]

Summary

On x86-64 with clang 3.8, before:

mov     edx, 1
mov     cl, dil
shl     rdx, cl
cmp     rdi, 64
mov     rax, -1
cmovne  rax, rdx
ret

after:

mov     ecx, 64
sub     ecx, edi
mov     rax, -1
shr     rax, cl
ret

[majnemer]

LGTM with nits.

include/llvm/Support/MathExtras.h

323 ↗

(On Diff #64232)

~UINT64_C(0) could be written as UINT_MAX

[jlebar]

Use UINT64_MAX.

include/llvm/Support/MathExtras.h

323 ↗

(On Diff #64232)

Oh. That is better.

Thank you for the review!

[krasin]

FYI: this made UBSan bot unhappy: http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/14727/steps/check-llvm%20ubsan/logs/stdio

[ RUN      ] MathExtras.minIntN
/mnt/b/sanitizer-buildbot3/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/MathExtras.h:340:10: runtime error: negation of -9223372036854775808 cannot be represented in type 'long'; cast to an unsigned type to negate this value to itself
    #0 0x4fb9e3 in llvm::minIntN(long) /mnt/b/sanitizer-buildbot3/sanitizer-x86_64-linux-fast/build/llvm/include/llvm/Support/MathExtras.h:340:10

[jlebar]

this made UBSan bot unhappy

FYI I think it was probably the patch I checked in to add tests for minIntN, D22443. Hooray for tests.

llvm/trunk/include/llvm/Support/MathExtras.h

 inline bool isShiftedUInt(uint64_t x) {
   return isUInt<N+S>(x) && (x % (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.
-  if (N == 64)
-    return std::numeric_limits<uint64_t>::max();
-  return (UINT64_C(1) << N) - 1;
+  // uint64_t(1) << 64 is undefined behavior, so we can't do
+  //   (uint64_t(1) << N) - 1
+  // without checking first that N != 64.  But this works and doesn't have a
+  // branch.
+  return UINT64_MAX >> (64 - N);
 }
 
 /// Gets the minimum value for a N-bit signed integer.
 inline int64_t minIntN(int64_t N) {
   assert(N > 0 && N <= 64 && "integer width out of range");
 
   return -(INT64_C(1)<<(N-1));
 }