[NFC][compiler-rt] Factor out __div[sdt]i3 and __mod[dt]i3 implementations

[atrosinenko]

Summary

An attempt was made to generically recreate these functions as close to the original implementations as possible to reduce possibility of performance any regression.

This patch is intended to simplify implementation of 16-bit integer division/multiplication LibCalls required on 16-bit targets and fixing some UB.

[MaskRay]

LG

compiler-rt/lib/builtins/divdi3.c

 //===-- divdi3.c - Implement __divdi3 -------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements __divdi3 for the compiler_rt library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 // Returns: a / b
 
-COMPILER_RT_ABI di_int __divdi3(di_int a, di_int b) {
-  const int bits_in_dword_m1 = (int)(sizeof(di_int) * CHAR_BIT) - 1;
-  di_int s_a = a >> bits_in_dword_m1;                   // s_a = a < 0 ? -1 : 0
-  di_int s_b = b >> bits_in_dword_m1;                   // 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 (__udivmoddi4(a, b, (du_int *)0) ^ s_a) - s_a; // negate if s_a == -1
-}
+#define fixint_t di_int
+#define fixuint_t du_int
+#define COMPUTE_UDIV(a, b) __udivmoddi4((a), (b), (du_int *)0)
+#include "int_div_impl.inc"
+
+COMPILER_RT_ABI di_int __divdi3(di_int a, di_int b) { return __divXi3(a, b); }

compiler-rt/lib/builtins/divsi3.c

 //===-- divsi3.c - Implement __divsi3 -------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements __divsi3 for the compiler_rt library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 // Returns: a / b
 
-COMPILER_RT_ABI si_int __divsi3(si_int a, si_int b) {
-  const int bits_in_word_m1 = (int)(sizeof(si_int) * CHAR_BIT) - 1;
-  si_int s_a = a >> bits_in_word_m1; // s_a = a < 0 ? -1 : 0
-  si_int s_b = b >> bits_in_word_m1; // 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
-  //
-  // On CPUs without unsigned hardware division support,
-  //  this calls __udivsi3 (notice the cast to su_int).
-  // On CPUs with unsigned hardware division support,
-  //  this uses the unsigned division instruction.
-  //
-  return ((su_int)a / (su_int)b ^ s_a) - s_a; // negate if s_a == -1
-}
+#define fixint_t si_int
+#define fixuint_t su_int
+#define COMPUTE_UDIV(a, b) ((su_int)(a) / (su_int)(b))
+#include "int_div_impl.inc"
+
+COMPILER_RT_ABI si_int __divsi3(si_int a, si_int b) { return __divXi3(a, b); }
 
 #if defined(__ARM_EABI__)
 COMPILER_RT_ALIAS(__divsi3, __aeabi_idiv)
 #endif

compiler-rt/lib/builtins/divti3.c

 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 #ifdef CRT_HAS_128BIT
 
 // Returns: a / b
 
-COMPILER_RT_ABI ti_int __divti3(ti_int a, ti_int b) {
-  const int bits_in_tword_m1 = (int)(sizeof(ti_int) * CHAR_BIT) - 1;
-  ti_int s_a = a >> bits_in_tword_m1;                   // s_a = a < 0 ? -1 : 0
-  ti_int s_b = b >> bits_in_tword_m1;                   // 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 (__udivmodti4(a, b, (tu_int *)0) ^ s_a) - s_a; // negate if s_a == -1
-}
+#define fixint_t ti_int
+#define fixuint_t tu_int
+#define COMPUTE_UDIV(a, b) __udivmodti4((a), (b), (tu_int *)0)
+#include "int_div_impl.inc"
+
+COMPILER_RT_ABI ti_int __divti3(ti_int a, ti_int b) { return __divXi3(a, b); }
 
 #endif // CRT_HAS_128BIT

compiler-rt/lib/builtins/int_div_impl.inc

for (; sr > 0; --sr) {
     // 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;
   }
   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
+}
+#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
+  fixuint_t res;
+  ASSIGN_UMOD(res, a, b);
+  return (res ^ s) - s;   // negate if s == -1
+}
+#endif // ASSIGN_UMOD

compiler-rt/lib/builtins/moddi3.c

 //===-- moddi3.c - Implement __moddi3 -------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements __moddi3 for the compiler_rt library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 // Returns: a % b
 
-COMPILER_RT_ABI di_int __moddi3(di_int a, di_int b) {
-  const int bits_in_dword_m1 = (int)(sizeof(di_int) * CHAR_BIT) - 1;
-  di_int s = b >> bits_in_dword_m1; // s = b < 0 ? -1 : 0
-  b = (b ^ s) - s;                  // negate if s == -1
-  s = a >> bits_in_dword_m1;        // s = a < 0 ? -1 : 0
-  a = (a ^ s) - s;                  // negate if s == -1
-  du_int r;
-  __udivmoddi4(a, b, &r);
-  return ((di_int)r ^ s) - s; // negate if s == -1
-}
+#define fixint_t di_int
+#define fixuint_t du_int
+#define ASSIGN_UMOD(res, a, b) __udivmoddi4((a), (b), &(res))
+#include "int_div_impl.inc"
+
+COMPILER_RT_ABI di_int __moddi3(di_int a, di_int b) { return __modXi3(a, b); }

compiler-rt/lib/builtins/modti3.c

 //===----------------------------------------------------------------------===//
 
 #include "int_lib.h"
 
 #ifdef CRT_HAS_128BIT
 
 // Returns: a % b
 
-COMPILER_RT_ABI ti_int __modti3(ti_int a, ti_int b) {
-  const int bits_in_tword_m1 = (int)(sizeof(ti_int) * CHAR_BIT) - 1;
-  ti_int s = b >> bits_in_tword_m1; // s = b < 0 ? -1 : 0
-  b = (b ^ s) - s;                  // negate if s == -1
-  s = a >> bits_in_tword_m1;        // s = a < 0 ? -1 : 0
-  a = (a ^ s) - s;                  // negate if s == -1
-  tu_int r;
-  __udivmodti4(a, b, &r);
-  return ((ti_int)r ^ s) - s; // negate if s == -1
-}
+#define fixint_t ti_int
+#define fixuint_t tu_int
+#define ASSIGN_UMOD(res, a, b) __udivmodti4((a), (b), &(res))
+#include "int_div_impl.inc"
+
+COMPILER_RT_ABI ti_int __modti3(ti_int a, ti_int b) { return __modXi3(a, b); }
 
 #endif // CRT_HAS_128BIT