[builtins] Add 32-bit shift builtins

[aykevl]

Summary

This patch adds support for the following 32-bit shift builtins:

• __ashlsi3
• __ashrsi3
• __lshrsi3

They are needed on architectures that do not have a 32-bit shift instruction, such as AVR.

---

Note: this patch depends on D78662.

[MaskRay]

Shall we factor out the common part of lshrti3.c and lshrdi3.c and place that in an .inc file? We can thus avoid duplication.

compiler-rt/lib/builtins/lshrsi3.c

24

Prefer BCPL-style // comments to C-style /* */

if (...) {
  // Comment
  ...
} else {
  // Comment
  ...
}

compiler-rt/test/builtins/Unit/lshrsi3_test.c

24

Place { in the end of the previous line.

26

The LLVM coding standard uses indent=2. I know that certain compiler-rt are using 4, but for new files, we probably should stick with indent=2.

[aykevl]

• formatted test files with clang-format
• moved shift implementations into common _impl.inc files
• fixed comment style of shift implementations (// instead of /* ... */)

I believe that addresses all review comments.

[MaskRay]

compiler-rt/test/builtins/Unit/ashlsi3_test.c

4

Test files don't need file headers. There are plenty of examples in clang/test/

compiler-rt/test/builtins/Unit/ashrsi3_test.c

4

ditto

[aykevl]

compiler-rt/test/builtins/Unit/ashlsi3_test.c

4

All the other compiler-rt builtins tests (compiler-rt/test/builtins/Unit/*_test.c) do have a header. Should I deviate from that convention for new files?

One difference between these tests and the Clang tests is that these tests are in some sense full programs (with main) while Clang tests are usually just small incomplete source files, just testing whether the correct IR is generated.

(This file is a modified version of ashldi3_test.c, hence the style it follows).

[aykevl]

@MaskRay ping?

Also, I was wondering about those lint checks. I can apply them, but IMHO they reduce readability.

[MaskRay]

compiler-rt/lib/builtins/int_ashl_impl.inc

13 ↗

(On Diff #259616)

Use inline. We compile these files with -std=c11 (inline is a C99 keyword)

compiler-rt/test/builtins/Unit/ashlsi3_test.c

4

I think you can deviate from them. They apparently deviate from the common practice in llvm.

REQUIRES: should be place at the top.

34

It may be simpler organizing all tests in an array of arrays.

[aykevl]

• Changed __inline to inline
• Put REQUIRES line at the top

I'm not so sure about moving to an array of arrays. Coming from a Go background I'm used to this pattern (called "table driven tests") and I normally prefer it, but this pattern is rarely used in compiler-rt builtin tests and in particular is not used in the 64-bit versions of these tests (from which the 32-bit tests were derived: they are essentially the same tests but with shortened inputs).

[luismarques]

compiler-rt/lib/builtins/int_types.h

37–56

Are these macro definitions processor-specific? If so, can't we use something more general?

[aykevl]

compiler-rt/lib/builtins/int_types.h

37–56

I'm not sure what YUGA means exactly. The constants are defined in int_endianness.h and are also used in various other places in int_types.h (this file). I'm just following the existing convention.

[aykevl]

ping?

[atrosinenko]

A bit of comment fine-tuning. :)

UPD: Hmm, trivial "suggested changes" without any comment attached are rendered as a completely empty entries here (they are shown OK inline)...

compiler-rt/lib/builtins/ashrsi3.c

22

compiler-rt/test/builtins/Unit/ashlsi3_test.c

21

compiler-rt/test/builtins/Unit/ashrsi3_test.c

21

compiler-rt/test/builtins/Unit/lshrsi3_test.c

21

[atrosinenko]

Thanks @aykevl! This could be useful for MSP430 as well. Especially, the tests would be worth reusing even for target-specific assembly re-implementation of these routines.

Another bit of "non functional" comments.

compiler-rt/lib/builtins/int_ashl_impl.inc

14 ↗

(On Diff #272721)

As I understand, different widths were mentioned in bits_in_?word for different LibCalls (such as bits_in_dword for __ashlti3). Maybe something more generic such as half_width_bits would fit better.

19 ↗

(On Diff #272721)

Then, this could be written as half_width_bits <= b < , hmm, total_bits - not actually declared as a constant, but hopefully would be useful for clarity.

[aykevl]

I have fixed this in a different way for AVR, by expanding these instructions inline (just like avr-gcc does): D96677. Therefore, I don't plan on working on this change anymore.

@atrosinenko if you want to continue working on this patch (and fix the various issues you found), feel free to take over the patch. You can do this by commandeering it (Add Action -> Commandeer Revision).

[aykevl]

Not necessary anymore for AVR so abandoning. Anyone: feel free to use this patch however you see fit.

compiler-rt/lib/builtins/CMakeLists.txt

set(GENERIC_SOURCES
   adddf3.c
   addsf3.c
   addtf3.c
   addvdi3.c
   addvsi3.c
   addvti3.c
   apple_versioning.c
   ashldi3.c
+  ashlsi3.c
   ashlti3.c
   ashrdi3.c
+  ashrsi3.c
   ashrti3.c
   bswapdi2.c
   bswapsi2.c
   clzdi2.c
   clzsi2.c
   clzti2.c
   cmpdi2.c
   cmpti2.c
set(GENERIC_SOURCES
   floatundisf.c
   floatunsidf.c
   floatunsisf.c
   floatuntidf.c
   floatuntisf.c
   fp_mode.c
   int_util.c
   lshrdi3.c
+  lshrsi3.c
   lshrti3.c
   moddi3.c
   modsi3.c
   modti3.c
   muldc3.c
   muldf3.c
   muldi3.c
   mulodi4.c

compiler-rt/lib/builtins/ashlsi3.c

+// ====-- ashlsi3.c - Implement __ashlsi3 ---------------------------------===//
+//
+// 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 __ashlsi3 for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "int_lib.h"
+
+// Returns: a << b
+
+// Preconsition:  0 <= b < bits_in_sword
+
+COMPILER_RT_ABI si_int __ashlsi3(si_int a, int b) {
+  const int bits_in_word = (int)(sizeof(hi_int) * CHAR_BIT);
+  swords input;
+  swords result;
+  input.all = a;
+  if (b & bits_in_word) /* bits_in_word <= b < bits_in_sword */ {
+    result.s.low = 0;
+    result.s.high = input.s.low << (b - bits_in_word);
+  } else /* 0 <= b < bits_in_word */ {
+    if (b == 0)
+      return a;
+    result.s.low = input.s.low << b;
+    result.s.high = (input.s.high << b) | (input.s.low >> (bits_in_word - b));
+  }
+  return result.all;
+}

compiler-rt/lib/builtins/ashrsi3.c

+//===-- ashrsi3.c - Implement __ashrsi3 -----------------------------------===//
+//
+// 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 __ashrsi3 for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "int_lib.h"
+
+// Returns: arithmetic a >> b
+
+// Precondition:  0 <= b < bits_in_dword
+
+COMPILER_RT_ABI si_int __ashrsi3(si_int a, int b) {
+  const int bits_in_word = (int)(sizeof(hi_int) * CHAR_BIT);
+  swords input;
+  swords result;
+  input.all = a;
+  if (b & bits_in_word) /* bits_in_word <= b < bits_in_sword */ {
+    // result.s.high = input.s.high < 0 ? -1 : 0
+    result.s.high = input.s.high >> (bits_in_word - 1);
+    result.s.low = input.s.high >> (b - bits_in_word);
+  } else /* 0 <= b < bits_in_word */ {
+    if (b == 0)
+      return a;
+    result.s.high = input.s.high >> b;
+    result.s.low = (input.s.high << (bits_in_word - b)) | (input.s.low >> b);
+  }
+  return result.all;
+}

compiler-rt/lib/builtins/int_types.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef INT_TYPES_H
 #define INT_TYPES_H
 
 #include "int_endianness.h"
 
+typedef int16_t hi_int;
+typedef uint16_t hu_int;
+
 // 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;
 
 typedef int64_t di_int;
 typedef uint64_t du_int;
 
 typedef union {
+  si_int all;
+  struct {
+#if _YUGA_LITTLE_ENDIAN
+    hu_int low;
+    hi_int high;
+#else
+    hi_int high;
+    hu_int low;
+#endif // _YUGA_LITTLE_ENDIAN
+  } s;
+} swords;
+
+typedef union {
+  su_int all;
+  struct {
+#if _YUGA_LITTLE_ENDIAN
+    hu_int low;
+    hu_int high;
+#else
+    hu_int high;
+    hu_int low;
+#endif // _YUGA_LITTLE_ENDIAN
+  } s;
+} uswords;
+
+typedef union {
   di_int all;
   struct {
 #if _YUGA_LITTLE_ENDIAN
     su_int low;
     si_int high;
 #else
     si_int high;
     su_int low;

compiler-rt/lib/builtins/lshrsi3.c

+//===-- lshrsi3.c - Implement __lshrsi3 -----------------------------------===//
+//
+// 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 __lshrsi3 for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "int_lib.h"
+
+// Returns: logical a >> b
+
+// Precondition:  0 <= b < bits_in_sword
+
+COMPILER_RT_ABI si_int __lshrsi3(si_int a, int b) {
+  const int bits_in_word = (int)(sizeof(hi_int) * CHAR_BIT);
+  uswords input;
+  uswords result;
+  input.all = a;
+  if (b & bits_in_word) /* bits_in_word <= b < bits_in_sword */ {
+    result.s.high = 0;
+    result.s.low = input.s.high >> (b - bits_in_word);
+  } else /* 0 <= b < bits_in_word */ {
+    if (b == 0)
+      return a;
+    result.s.high = input.s.high >> b;
+    result.s.low = (input.s.high << (bits_in_word - b)) | (input.s.low >> b);
+  }
+  return result.all;
+}

compiler-rt/test/builtins/Unit/ashlsi3_test.c

+// RUN: %clang_builtins %s %librt -o %t && %run %t
+// REQUIRES: librt_has_ashlsi3
+//===-- ashlsi3_test.c - Test __ashlsi3 -----------------------------------===//
+//
+// 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 tests __ashlsi3 for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "int_lib.h"
+#include <stdio.h>
+
+// Returns: a << b
+
+// Precondition:  0 <= b < bits_in_dword
+
+COMPILER_RT_ABI si_int __ashlsi3(si_int a, int b);
+
+int test__ashlsi3(si_int a, int b, si_int expected)
+{
+    si_int x = __ashlsi3(a, b);
+    if (x != expected)
+        printf("error in __ashlsi3: %X << %d = %X, expected %X\n",
+               a, b, __ashlsi3(a, b), expected);
+    return x != expected;
+}
+
+int main()
+{
+    if (test__ashlsi3(0x01234567, 0, 0x1234567))
+        return 1;
+    if (test__ashlsi3(0x01234567, 1, 0x2468ACE))
+        return 1;
+    if (test__ashlsi3(0x01234567, 2, 0x048D159C))
+        return 1;
+    if (test__ashlsi3(0x01234567, 3, 0x091A2B38))
+        return 1;
+    if (test__ashlsi3(0x01234567, 4, 0x12345670))
+        return 1;
+
+    if (test__ashlsi3(0x01234567, 12, 0x34567000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 13, 0x68ACE000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 14, 0xD159C000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 15, 0xA2B38000))
+        return 1;
+
+    if (test__ashlsi3(0x01234567, 16, 0x45670000))
+        return 1;
+
+    if (test__ashlsi3(0x01234567, 17, 0x8ACE0000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 18, 0x159C0000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 19, 0x2B380000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 20, 0x56700000))
+        return 1;
+
+    if (test__ashlsi3(0x01234567, 28, 0x70000000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 29, 0xE0000000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 30, 0xC0000000))
+        return 1;
+    if (test__ashlsi3(0x01234567, 31, 0x80000000))
+        return 1;
+    return 0;
+}

compiler-rt/test/builtins/Unit/ashrsi3_test.c

+// RUN: %clang_builtins %s %librt -o %t && %run %t
+// REQUIRES: librt_has_ashrsi3
+//===-- ashrsi3_test.c - Test __ashrsi3 -----------------------------------===//
+//
+// 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 tests __ashrsi3 for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "int_lib.h"
+#include <stdio.h>
+
+// Returns: arithmetic a >> b
+
+// Precondition:  0 <= b < bits_in_dword
+
+COMPILER_RT_ABI si_int __ashrsi3(si_int a, int b);
+
+int test__ashrsi3(si_int a, int b, si_int expected)
+{
+    si_int x = __ashrsi3(a, b);
+    if (x != expected)
+        printf("error in __ashrsi3: %X >> %d = %X, expected %X\n",
+               a, b, __ashrsi3(a, b), expected);
+    return x != expected;
+}
+
+int main()
+{
+    if (test__ashrsi3(0x01234567, 0, 0x1234567))
+        return 1;
+    if (test__ashrsi3(0x01234567, 1, 0x91A2B3))
+        return 1;
+    if (test__ashrsi3(0x01234567, 2, 0x48D159))
+        return 1;
+    if (test__ashrsi3(0x01234567, 3, 0x2468AC))
+        return 1;
+    if (test__ashrsi3(0x01234567, 4, 0x123456))
+        return 1;
+
+    if (test__ashrsi3(0x01234567, 12, 0x1234))
+        return 1;
+    if (test__ashrsi3(0x01234567, 13, 0x91A))
+        return 1;
+    if (test__ashrsi3(0x01234567, 14, 0x48D))
+        return 1;
+    if (test__ashrsi3(0x01234567, 15, 0x246))
+        return 1;
+
+    if (test__ashrsi3(0x01234567, 16, 0x123))
+        return 1;
+
+    if (test__ashrsi3(0x01234567, 17, 0x91))
+        return 1;
+    if (test__ashrsi3(0x01234567, 18, 0x48))
+        return 1;
+    if (test__ashrsi3(0x01234567, 19, 0x24))
+        return 1;
+    if (test__ashrsi3(0x01234567, 20, 0x12))
+        return 1;
+
+    if (test__ashrsi3(0x01234567, 28, 0))
+        return 1;
+    if (test__ashrsi3(0x01234567, 29, 0))
+        return 1;
+    if (test__ashrsi3(0x01234567, 30, 0))
+        return 1;
+    if (test__ashrsi3(0x01234567, 31, 0))
+        return 1;
+
+    if (test__ashrsi3(0xFEDCBA98, 0, 0xFEDCBA98))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 1, 0xFF6E5D4C))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 2, 0xFFB72EA6))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 3, 0xFFDB9753))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 4, 0xFFEDCBA9))
+        return 1;
+
+    if (test__ashrsi3(0xFEDCBA98, 12, 0xFFFFEDCB))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 13, 0xFFFFF6E5))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 14, 0xFFFFFB72))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 15, 0xFFFFFDB9))
+        return 1;
+
+    if (test__ashrsi3(0xFEDCBA98, 16, 0xFFFFFEDC))
+        return 1;
+
+    if (test__ashrsi3(0xFEDCBA98, 17, 0xFFFFFF6E))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 18, 0xFFFFFFB7))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 19, 0xFFFFFFDB))
+        return 1;
+    if (test__ashrsi3(0xFEDCBA98, 20, 0xFFFFFFED))
+        return 1;
+
+    if (test__ashrsi3(0xAEDCBA98, 28, 0xFFFFFFFA))
+        return 1;
+    if (test__ashrsi3(0xAEDCBA98, 29, 0xFFFFFFFD))
+        return 1;
+    if (test__ashrsi3(0xAEDCBA98, 30, 0xFFFFFFFE))
+        return 1;
+    if (test__ashrsi3(0xAEDCBA98, 31, 0xFFFFFFFF))
+        return 1;
+    return 0;
+}

compiler-rt/test/builtins/Unit/lshrsi3_test.c

+// RUN: %clang_builtins %s %librt -o %t && %run %t
+// REQUIRES: librt_has_lshrsi3
+//===-- lshrsi3_test.c - Test __lshrsi3 -----------------------------------===//
+//
+// 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 tests __lshrsi3 for the compiler_rt library.
+//
+//===----------------------------------------------------------------------===//
+
+#include "int_lib.h"
+#include <stdio.h>
+
+// Returns: logical a >> b
+
+// Precondition:  0 <= b < bits_in_dword
+
+COMPILER_RT_ABI si_int __lshrsi3(si_int a, int b);
+
+int test__lshrsi3(si_int a, int b, si_int expected)
+{
+    si_int x = __lshrsi3(a, b);
+    if (x != expected)
+        printf("error in __lshrsi3: %X >> %d = %X, expected %X\n",
+               a, b, __lshrsi3(a, b), expected);
+    return x != expected;
+}
+
+int main()
+{
+    if (test__lshrsi3(0x01234567, 0, 0x1234567))
+        return 1;
+    if (test__lshrsi3(0x01234567, 1, 0x91A2B3))
+        return 1;
+    if (test__lshrsi3(0x01234567, 2, 0x48D159))
+        return 1;
+    if (test__lshrsi3(0x01234567, 3, 0x2468AC))
+        return 1;
+    if (test__lshrsi3(0x01234567, 4, 0x123456))
+        return 1;
+
+    if (test__lshrsi3(0x01234567, 12, 0x1234))
+        return 1;
+    if (test__lshrsi3(0x01234567, 13, 0x91A))
+        return 1;
+    if (test__lshrsi3(0x01234567, 14, 0x48D))
+        return 1;
+    if (test__lshrsi3(0x01234567, 15, 0x246))
+        return 1;
+
+    if (test__lshrsi3(0x01234567, 16, 0x123))
+        return 1;
+
+    if (test__lshrsi3(0x01234567, 17, 0x91))
+        return 1;
+    if (test__lshrsi3(0x01234567, 18, 0x48))
+        return 1;
+    if (test__lshrsi3(0x01234567, 19, 0x24))
+        return 1;
+    if (test__lshrsi3(0x01234567, 20, 0x12))
+        return 1;
+
+    if (test__lshrsi3(0x01234567, 28, 0))
+        return 1;
+    if (test__lshrsi3(0x01234567, 29, 0))
+        return 1;
+    if (test__lshrsi3(0x01234567, 30, 0))
+        return 1;
+    if (test__lshrsi3(0x01234567, 31, 0))
+        return 1;
+
+    if (test__lshrsi3(0xFEDCBA98, 0, 0xFEDCBA98))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 1, 0x7F6E5D4C))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 2, 0x3FB72EA6))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 3, 0x1FDB9753))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 4, 0xFEDCBA9))
+        return 1;
+
+    if (test__lshrsi3(0xFEDCBA98, 12, 0xFEDCB))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 13, 0x7F6E5))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 14, 0x3FB72))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 15, 0x1FDB9))
+        return 1;
+
+    if (test__lshrsi3(0xFEDCBA98, 16, 0xFEDC))
+        return 1;
+
+    if (test__lshrsi3(0xFEDCBA98, 17, 0x7F6E))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 18, 0x3FB7))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 19, 0x1FDB))
+        return 1;
+    if (test__lshrsi3(0xFEDCBA98, 20, 0xFED))
+        return 1;
+
+    if (test__lshrsi3(0xAEDCBA98, 28, 0xA))
+        return 1;
+    if (test__lshrsi3(0xAEDCBA98, 29, 0x5))
+        return 1;
+    if (test__lshrsi3(0xAEDCBA98, 30, 0x2))
+        return 1;
+    if (test__lshrsi3(0xAEDCBA98, 31, 0x1))
+        return 1;
+    return 0;
+}