Index: cmake/config-ix.cmake
===================================================================
--- cmake/config-ix.cmake
+++ cmake/config-ix.cmake
@@ -53,6 +53,11 @@
 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)
Index: lib/builtins/CMakeLists.txt
===================================================================
--- lib/builtins/CMakeLists.txt
+++ lib/builtins/CMakeLists.txt
@@ -136,6 +136,7 @@
   subvsi3.c
   subvti3.c
   subtf3.c
+  sparsetable.c
   trampoline_setup.c
   truncdfhf2.c
   truncdfsf2.c
Index: lib/builtins/sparsetable.c
===================================================================
--- /dev/null
+++ lib/builtins/sparsetable.c
@@ -0,0 +1,130 @@
+/* ===-- 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
Index: lib/builtins/sparsetableimpl.h
===================================================================
--- /dev/null
+++ lib/builtins/sparsetableimpl.h
@@ -0,0 +1,27 @@
+/* ===-- 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];