[compiler-rt][builtins] Fix some other cases of UB

[atrosinenko]

Summary

This patch eliminates some other UB in a slightly more tricky way than D86299: [compiler-rt][builtins] Factor out some common bit manipulations.

• Introduce a SIGN_OF(signed_int) macro (not UB-related, just to give this trick a descriptive name)
• Make the "negate if sign is -1" trick operate on corresponding unsigned types. Not factoring it out due to the "interface" of that macro would probably be quite error-prone.

This patch is expected to be NFC except for eliminating some UB identified by unit tests.

[atrosinenko]

Re-upload with properly set parent review.

compiler-rt/lib/builtins/absvdi2.c

 
 #include "int_lib.h"
 
 // Returns: absolute value
 
 // Effects: aborts if abs(x) < 0
 
 COMPILER_RT_ABI di_int __absvdi2(di_int a) {
-  const int N = (int)(sizeof(di_int) * CHAR_BIT);
-  if (a == ((di_int)1 << (N - 1)))
+  if (a == MIN_SIGNED(di_int))
     compilerrt_abort();
-  const di_int t = a >> (N - 1);
-  return (a ^ t) - t;
+  const di_int t = SIGN_OF(a);
+  return (du_int)(a ^ t) - (du_int)t;
 }

compiler-rt/lib/builtins/absvsi2.c

 
 #include "int_lib.h"
 
 // Returns: absolute value
 
 // Effects: aborts if abs(x) < 0
 
 COMPILER_RT_ABI si_int __absvsi2(si_int a) {
-  const int N = (int)(sizeof(si_int) * CHAR_BIT);
-  if (a == ((si_int)1 << (N - 1)))
+  if (a == MIN_SIGNED(si_int))
     compilerrt_abort();
-  const si_int t = a >> (N - 1);
-  return (a ^ t) - t;
+  const si_int t = SIGN_OF(a);
+  return (su_int)(a ^ t) - (su_int)t;
 }

compiler-rt/lib/builtins/absvti2.c

 
 #ifdef CRT_HAS_128BIT
 
 // Returns: absolute value
 
 // Effects: aborts if abs(x) < 0
 
 COMPILER_RT_ABI ti_int __absvti2(ti_int a) {
-  const int N = (int)(sizeof(ti_int) * CHAR_BIT);
-  if (a == ((ti_int)1 << (N - 1)))
+  if (a == MIN_SIGNED(ti_int))
     compilerrt_abort();
-  const ti_int s = a >> (N - 1);
-  return (a ^ s) - s;
+  const ti_int t = SIGN_OF(a);
+  return (tu_int)(a ^ t) - (tu_int)t;
 }
 
 #endif // CRT_HAS_128BIT

compiler-rt/lib/builtins/floattidf.c

 //            ti_int is a 128 bit integral type
 
 // seee eeee eeee mmmm mmmm mmmm mmmm mmmm | mmmm mmmm mmmm mmmm mmmm mmmm mmmm
 // mmmm
 
 COMPILER_RT_ABI double __floattidf(ti_int a) {
   if (a == 0)
     return 0.0;
-  const unsigned N = sizeof(ti_int) * CHAR_BIT;
-  const ti_int s = a >> (N - 1);
-  a = (a ^ s) - s;
+  const unsigned N = bitsizeof(ti_int);
+  const ti_int s = SIGN_OF(a);
+  a = (tu_int)(a ^ s) - (tu_int)s;
   int sd = N - __clzti2(a); // number of significant digits
   int e = sd - 1;           // exponent
   if (sd > DBL_MANT_DIG) {
     // start:  0000000000000000000001xxxxxxxxxxxxxxxxxxxxxxPQxxxxxxxxxxxxxxxxxx
     //  finish: 000000000000000000000000000000000000001xxxxxxxxxxxxxxxxxxxxxxPQR
     //                                               12345678901234567890123456
     // 1 = msb 1 bit
     // P = bit DBL_MANT_DIG-1 bits to the right of 1

compiler-rt/lib/builtins/floattixf.c

 
 // gggg gggg gggg gggg gggg gggg gggg gggg | gggg gggg gggg gggg seee eeee eeee
 // eeee | 1mmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm | mmmm mmmm mmmm mmmm mmmm
 // mmmm mmmm mmmm
 
 COMPILER_RT_ABI long double __floattixf(ti_int a) {
   if (a == 0)
     return 0.0;
-  const unsigned N = sizeof(ti_int) * CHAR_BIT;
-  const ti_int s = a >> (N - 1);
-  a = (a ^ s) - s;
+  const unsigned N = bitsizeof(ti_int);
+  const ti_int s = SIGN_OF(a);
+  a = (tu_int)(a ^ s) - (tu_int)s;
   int sd = N - __clzti2(a); // number of significant digits
   int e = sd - 1;           // exponent
   if (sd > LDBL_MANT_DIG) {
     //  start:  0000000000000000000001xxxxxxxxxxxxxxxxxxxxxxPQxxxxxxxxxxxxxxxxxx
     //  finish: 000000000000000000000000000000000000001xxxxxxxxxxxxxxxxxxxxxxPQR
     //                                                12345678901234567890123456
     //  1 = msb 1 bit
     //  P = bit LDBL_MANT_DIG-1 bits to the right of 1

compiler-rt/lib/builtins/int_div_impl.inc

 //===-- int_div_impl.inc - Integer division ---------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Helpers used by __udivsi3, __umodsi3, __udivdi3, and __umodsi3.
 //
 //===----------------------------------------------------------------------===//
 
 #define clz(a) (sizeof(a) == sizeof(unsigned long long) ? __builtin_clzll(a) : clzsi(a))
 
 // Adapted from Figure 3-40 of The PowerPC Compiler Writer's Guide
 static __inline fixuint_t __udivXi3(fixuint_t n, fixuint_t d) {
   const unsigned N = sizeof(fixuint_t) * CHAR_BIT;
   // d == 0 cases are unspecified.
   unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N);
   // 0 <= sr <= N - 1 or sr is very large.
   if (sr > N - 1) // n < d
     return 0;
   if (sr == N - 1) // d == 1
     return n;
   ++sr;
   // 1 <= sr <= N - 1. Shifts do not trigger UB.
   fixuint_t r = n >> sr;
   n <<= N - sr;
   fixuint_t carry = 0;
   for (; sr > 0; --sr) {
     r = (r << 1) | (n >> (N - 1));
     n = (n << 1) | carry;
     // Branch-less version of:
     // carry = 0;
     // if (r >= d) r -= d, carry = 1;
     const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1);
     carry = s & 1;
     r -= d & s;
   }
   n = (n << 1) | carry;
   return n;
 }
 
 // Mostly identical to __udivXi3 but the return values are different.
 static __inline fixuint_t __umodXi3(fixuint_t n, fixuint_t d) {
   const unsigned N = sizeof(fixuint_t) * CHAR_BIT;
   // d == 0 cases are unspecified.
   unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N);
   // 0 <= sr <= N - 1 or sr is very large.
   if (sr > N - 1) // n < d
     return n;
   if (sr == N - 1) // d == 1
     return 0;
for (; sr > 0; --sr) {
     carry = s & 1;
     r -= d & s;
   }
   return r;
 }
 
 #ifdef COMPUTE_UDIV
 static __inline fixint_t __divXi3(fixint_t a, fixint_t b) {
-  const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
-  fixint_t s_a = a >> N;                   // s_a = a < 0 ? -1 : 0
-  fixint_t s_b = b >> N;                   // s_b = b < 0 ? -1 : 0
-  a = (a ^ s_a) - s_a;                     // negate if s_a == -1
-  b = (b ^ s_b) - s_b;                     // negate if s_b == -1
-  s_a ^= s_b;                              // sign of quotient
-  return (COMPUTE_UDIV(a, b) ^ s_a) - s_a; // negate if s_a == -1
+  // extract signs (0 or -1) of arguments
+  fixint_t s_a = SIGN_OF(a);
+  fixint_t s_b = SIGN_OF(b);
+  // compute absolute values of arguments
+  a = (fixuint_t)(a ^ s_a) - (fixuint_t)s_a;
+  b = (fixuint_t)(b ^ s_b) - (fixuint_t)s_b;
+  // compute a sign of quotient
+  s_a ^= s_b;
+  // compute an absolute value of quotient and negate it if needed
+  return (fixuint_t)(COMPUTE_UDIV(a, b) ^ s_a) - (fixuint_t)s_a;
 }
 #endif // COMPUTE_UDIV
 
 #ifdef ASSIGN_UMOD
 static __inline fixint_t __modXi3(fixint_t a, fixint_t b) {
-  const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
-  fixint_t s = b >> N;    // s = b < 0 ? -1 : 0
-  b = (b ^ s) - s;        // negate if s == -1
-  s = a >> N;             // s = a < 0 ? -1 : 0
-  a = (a ^ s) - s;        // negate if s == -1
+  // compute an absolute value of b
+  fixint_t s = SIGN_OF(b);
+  b = (fixuint_t)(b ^ s) - (fixuint_t)s;
+  // compute an absolute value of a
+  s = SIGN_OF(a);
+  a = (fixuint_t)(a ^ s) - (fixuint_t)s;
+  // compute an absolute value of the result
   fixuint_t res;
   ASSIGN_UMOD(res, a, b);
-  return (res ^ s) - s;   // negate if s == -1
+  // make the result have the same sign as b
+  return (fixuint_t)(res ^ s) - (fixuint_t)s;
 }
 #endif // ASSIGN_UMOD

compiler-rt/lib/builtins/int_types.h

 #define INT_TYPES_H
 
 #include "int_endianness.h"
 
 // si_int is defined in Linux sysroot's asm-generic/siginfo.h
 #ifdef si_int
 #undef si_int
 #endif
 typedef int32_t si_int;
 typedef uint32_t su_int;
 #if UINT_MAX == 0xFFFFFFFF
 #define clzsi __builtin_clz
 #define ctzsi __builtin_ctz
 #elif ULONG_MAX == 0xFFFFFFFF
 #define clzsi __builtin_clzl
 #define ctzsi __builtin_ctzl
 #else
 #error could not determine appropriate clzsi macro for this system
 #endif
 
 typedef int64_t di_int;
 typedef uint64_t du_int;
 
 // Helpers for standard type aliases to get signed from unsigned and vice versa
 #define AS_SIGNED(type) type##_AS_SIGNED
 #define AS_UNSIGNED(type) type##_AS_UNSIGNED
 #define si_int_AS_SIGNED si_int
 #define su_int_AS_SIGNED si_int
 #define di_int_AS_SIGNED di_int
 #define du_int_AS_SIGNED di_int
 #define ti_int_AS_SIGNED ti_int
 #define tu_int_AS_SIGNED ti_int
 #define si_int_AS_UNSIGNED su_int
 #define su_int_AS_UNSIGNED su_int
 #define di_int_AS_UNSIGNED du_int
 #define du_int_AS_UNSIGNED du_int
 #define ti_int_AS_UNSIGNED tu_int
 #define tu_int_AS_UNSIGNED tu_int
 
 // Misc macroses incapsulating common hacks.
 // Supposed to replace the ad-hoc UB-prone implementations.
 #define bitsizeof(type_or_value) ((int)(sizeof(type_or_value) * CHAR_BIT))
 #define SIGN_BIT(type) ((AS_UNSIGNED(type))1 << (bitsizeof(type) - 1))
 #define MIN_SIGNED(type) ((AS_SIGNED(type))SIGN_BIT(type))
 #define MAX_SIGNED(type) ((AS_SIGNED(type))(SIGN_BIT(type) - 1U))
 #define MAX_UNSIGNED(type) (~(AS_UNSIGNED(type))0))
+#define SIGN_OF(signed_int) ((signed_int) >> (bitsizeof(signed_int) - 1))
 
 typedef union {
   di_int all;
   struct {
 #if _YUGA_LITTLE_ENDIAN
     su_int low;
     si_int high;
 #else