[builtins] run-time support for sparse maps in llvm

[shawnl]

Summary

I am trying to move towards much more space-efficient switch statements, using popcnt, as described in PR39013. This is the run-time component. See D60673 and D60982 Code that uses this is not ready for review, and is here: https://github.com/shawnl/llvm/tree/test

I am hoping on getting some feed-back on this implementation. compiler-rt is written to be very portable, and my patch depends on popcountll, a GNU extension, as well as eSymbolTypeResolver (IFUNC when using ELF). Also, I had planned to implement a dosparsejmp() that would directly jump after a tail call, instead of possibly just using __getsparse32/64 here, and that would require special code for every supported architecture. (but it will probably be necessary with non-integer pointer arches like Mill become part of LLVM)

This is a space-saving improvement, so putting these routines here make sense.

There are three versions, in 4 sizes (8 16 32 and 64 bits). The three versions are:

• normal: default is the same size as the elements of the table
• unreachable: default is unreachable, meaning some checks can be omitted
• code: default is code (gcc has this: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=58774 )

[jmolloy]

I am not the right person to review this change. I have never made changes in this directory and don't know enough about potential impact to LGTM.

[shawnl]

Make more portable

[shawnl]

made more portable

[shawnl]

I don't think this should use function pointers.

[hans]

I'm also not really familiar with code in compiler-rt.

However, as pointed out in https://bugs.llvm.org/show_bug.cgi?id=39013#c4 the compiler-rt builtins are not available for most targets.

I can mostly speak for Chromium, but in those builds we use libgcc on Linux, the Windows libraries on Windows, and on Mac we use the system's compiler-rt.

This means if you want to do any switch transformation that relies on this runtime function, that transformation will have to be disabled in general, and at that point I'm not sure it makes sense to have it in tree.

I'd suggest trying to emit the runtime code that your switch transformation relies on as LLVM IR instead. That might actually be easier, because e.g. you can rely on LLVM's popcount intrinsic, and you can do lower level stuff that is maybe useful.

[shawnl]

This will be put directly into LLVM-IR, as llvm can't inline it otherwise anyways.

cmake/config-ix.cmake

if (MINGW)
     set(MINGW_LIBRARIES mingw32 ${MINGW_RUNTIME} moldname mingwex msvcrt advapi32
                         shell32 user32 kernel32 mingw32 ${MINGW_RUNTIME}
                         moldname mingwex msvcrt)
     list(APPEND CMAKE_REQUIRED_LIBRARIES ${MINGW_LIBRARIES})
   endif()
 endif ()
 
 # CodeGen options.
+check_c_source_compiles("
+    #pragma GCC diagnostic error \"-Wattributes\"
+    void func() __attribute__((__target_clones__(\"popcnt,default\")));
+    int main() { return 0; }"
+COMPILER_RT_HAVE_IFUNC_TARGET_CLONES)
 check_c_compiler_flag(-ffreestanding         COMPILER_RT_HAS_FFREESTANDING_FLAG)
 check_cxx_compiler_flag(-fPIC                COMPILER_RT_HAS_FPIC_FLAG)
 check_cxx_compiler_flag(-fPIE                COMPILER_RT_HAS_FPIE_FLAG)
 check_cxx_compiler_flag(-fno-builtin         COMPILER_RT_HAS_FNO_BUILTIN_FLAG)
 check_cxx_compiler_flag(-fno-exceptions      COMPILER_RT_HAS_FNO_EXCEPTIONS_FLAG)
 check_cxx_compiler_flag(-fomit-frame-pointer COMPILER_RT_HAS_FOMIT_FRAME_POINTER_FLAG)
 check_cxx_compiler_flag(-funwind-tables      COMPILER_RT_HAS_FUNWIND_TABLES_FLAG)
 check_cxx_compiler_flag(-fno-stack-protector COMPILER_RT_HAS_FNO_STACK_PROTECTOR_FLAG)

lib/builtins/CMakeLists.txt

set(GENERIC_SOURCES
   powisf2.c
   powitf2.c
   subdf3.c
   subsf3.c
   subvdi3.c
   subvsi3.c
   subvti3.c
   subtf3.c
+  sparsetable.c
   trampoline_setup.c
   truncdfhf2.c
   truncdfsf2.c
   truncsfhf2.c
   ucmpdi2.c
   ucmpti2.c
   udivdi3.c
   udivmoddi4.c

lib/builtins/sparsetable.c

+/* ===-- sparsetable.c - Implement __getsparse* ----------------------------===
+ *
+ * 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 __getsparse(8|16|32|64)[cu]
+ * for the compiler_rt library.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+// Taken from fuzzer
+#include <stdint.h>
+#if defined(_MSC_VER) && !defined(__clang__)
+#include <intrin.h>
+inline int Popcountll(unsigned long long X) { return __popcnt64(X); }
+#else
+inline int Popcountll(unsigned long long X) { return __builtin_popcountll(X); }
+#endif
+
+struct sparse_table_entry {
+  uint32_t length; // x16 for bytes, only first entry
+  uint32_t running_count;
+  uint64_t bitmap;
+};
+
+uint8_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse8(uint8_t df, uint8_t index, const struct sparse_table_entry *restrict map, const uint8_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint16_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse16(uint16_t df, uint16_t index, const struct sparse_table_entry *restrict map, const uint16_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint32_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse32(uint32_t df, uint32_t index, const struct sparse_table_entry *restrict map, const uint32_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint64_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse64(uint64_t df, uint64_t index, const struct sparse_table_entry *restrict map, const uint64_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+#define DEFAULT_UNREACHABLE
+uint8_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse8u(uint8_t df, uint8_t index, const struct sparse_table_entry *restrict map, const uint8_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint16_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse16u(uint16_t df, uint16_t index, const struct sparse_table_entry *restrict map, const uint16_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint32_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse32u(uint32_t df, uint32_t index, const struct sparse_table_entry *restrict map, const uint32_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint64_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse64u(uint64_t df, uint64_t index, const struct sparse_table_entry *restrict map, const uint64_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+#undef DEFAULT_UNREACHABLE
+#define DEFAULT_CODE
+
+uint8_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse8c(uint8_t (*df)(), uint8_t index, const struct sparse_table_entry *restrict map, const uint8_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint16_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse16c(uint16_t (*df)(), uint16_t index, const struct sparse_table_entry *restrict map, const uint16_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint32_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparse32c(uint32_t (*df)(), uint32_t index, const struct sparse_table_entry *restrict map, const uint32_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+uint64_t
+#if defined(COMPILER_RT_HAVE_IFUNC_TARGET_CLONES) && (defined(__i386__) || defined(__amd64__))
+__attribute__((__target_clones__("popcnt,default")))
+#endif
+__getsparsec(uint64_t (*df)(), uint64_t index, const struct sparse_table_entry *restrict map, const uint64_t *restrict table) {
+#include "sparsetableimpl.h"
+}
+
+#undef DEFAULT_CODE

lib/builtins/sparsetableimpl.h

+/* ===-- sparsetableimpl.h - Implement __getsparse* ------------------------===
+ *
+ * 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
+ *
+ * ===----------------------------------------------------------------------===
+ *
+ * Deliberately NOT #pragma once
+ *
+ * ===----------------------------------------------------------------------===
+ */
+// Index range is limited to (1ULL << 38) - 1
+uint32_t outer = index / 64;
+uint32_t inner = index % 64;
+#ifndef DEFAULT_UNDEFINED
+if (outer >= map[0].length || (map[outer].bitmap & (1ULL << inner)) == 0) {
+#ifdef DEFAULT_CODE
+  return df();
+#else
+  return df;
+#endif /*DEFAULT_CODE*/
+}
+#endif /*DEFAULT_UNDEFINED*/
+uint64_t mask = ((uint64_t)(-1)) >> (63 - inner);
+uint32_t popcount = Popcountll(map[outer].bitmap & mask);
+return table[map[outer].running_count + popcount];