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,123 @@
+/* ===-- 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.
+ *
+ * ===----------------------------------------------------------------------===
+ */
+
+#include <stdint.h>
+
+struct sparse_table_entry {
+  uint32_t length; // x16 for bytes, only first entry
+  uint32_t running_count;
+  uint64_t bitmap;
+};
+
+uint8_t
+#if 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(__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(__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(__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(__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(__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(__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(__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(__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(__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(__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(__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 = __builtin_popcountll(map[outer].bitmap & mask);
+return table[map[outer].running_count + popcount];