diff --git a/libcxx/include/string.h b/libcxx/include/string.h
--- a/libcxx/include/string.h
+++ b/libcxx/include/string.h
@@ -71,41 +71,41 @@
 
 #if defined(__cplusplus) && !defined(_LIBCPP_STRING_H_HAS_CONST_OVERLOADS) && defined(_LIBCPP_PREFERRED_OVERLOAD)
 extern "C++" {
-inline _LIBCPP_INLINE_VISIBILITY
-char* __libcpp_strchr(const char* __s, int __c) {return (char*)strchr(__s, __c);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-const char* strchr(const char* __s, int __c) {return __libcpp_strchr(__s, __c);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-      char* strchr(      char* __s, int __c) {return __libcpp_strchr(__s, __c);}
-
-inline _LIBCPP_INLINE_VISIBILITY
-char* __libcpp_strpbrk(const char* __s1, const char* __s2) {return (char*)strpbrk(__s1, __s2);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-const char* strpbrk(const char* __s1, const char* __s2) {return __libcpp_strpbrk(__s1, __s2);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-      char* strpbrk(      char* __s1, const char* __s2) {return __libcpp_strpbrk(__s1, __s2);}
-
-inline _LIBCPP_INLINE_VISIBILITY
-char* __libcpp_strrchr(const char* __s, int __c) {return (char*)strrchr(__s, __c);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-const char* strrchr(const char* __s, int __c) {return __libcpp_strrchr(__s, __c);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-      char* strrchr(      char* __s, int __c) {return __libcpp_strrchr(__s, __c);}
-
-inline _LIBCPP_INLINE_VISIBILITY
-void* __libcpp_memchr(const void* __s, int __c, size_t __n) {return (void*)memchr(__s, __c, __n);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-const void* memchr(const void* __s, int __c, size_t __n) {return __libcpp_memchr(__s, __c, __n);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-      void* memchr(      void* __s, int __c, size_t __n) {return __libcpp_memchr(__s, __c, __n);}
-
-inline _LIBCPP_INLINE_VISIBILITY
-char* __libcpp_strstr(const char* __s1, const char* __s2) {return (char*)strstr(__s1, __s2);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-const char* strstr(const char* __s1, const char* __s2) {return __libcpp_strstr(__s1, __s2);}
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_PREFERRED_OVERLOAD
-      char* strstr(      char* __s1, const char* __s2) {return __libcpp_strstr(__s1, __s2);}
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD const char* strchr(const char* __s, int __c) {
+  return __builtin_strchr(__s, __c);
 }
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD char* strchr(char* __s, int __c) {
+  return __builtin_strchr(__s, __c);
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD const char* strpbrk(const char* __s1, const char* __s2) {
+  return __builtin_strpbrk(__s1, __s2);
+}
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD char* strpbrk(char* __s1, const char* __s2) {
+  return __builtin_strpbrk(__s1, __s2);
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD const char* strrchr(const char* __s, int __c) {
+  return __builtin_strrchr(__s, __c);
+}
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD char* strrchr(char* __s, int __c) {
+  return __builtin_strrchr(__s, __c);
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD const void* memchr(const void* __s, int __c, size_t __n) {
+  return __builtin_memchr(__s, __c, __n);
+}
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD void* memchr(void* __s, int __c, size_t __n) {
+  return __builtin_memchr(__s, __c, __n);
+}
+
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD const char* strstr(const char* __s1, const char* __s2) {
+  return __builtin_strstr(__s1, __s2);
+}
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_PREFERRED_OVERLOAD char* strstr(char* __s1, const char* __s2) {
+  return __builtin_strstr(__s1, __s2);
+}
+} // extern "C++"
 #endif
 
 #endif // _LIBCPP_STRING_H
diff --git a/libcxx/test/std/depr/depr.c.headers/string_h.pass.cpp b/libcxx/test/std/depr/depr.c.headers/string_h.pass.cpp
--- a/libcxx/test/std/depr/depr.c.headers/string_h.pass.cpp
+++ b/libcxx/test/std/depr/depr.c.headers/string_h.pass.cpp
@@ -9,6 +9,7 @@
 // <string.h>
 
 #include <string.h>
+#include <cassert>
 #include <type_traits>
 
 #include "test_macros.h"
@@ -19,38 +20,119 @@
 
 int main(int, char**)
 {
-    size_t s = 0;
-    void* vp = 0;
-    const void* vpc = 0;
-    char* cp = 0;
-    const char* cpc = 0;
-    ASSERT_SAME_TYPE(void*,         decltype(memcpy(vp, vpc, s)));
-    ASSERT_SAME_TYPE(void*,         decltype(memmove(vp, vpc, s)));
-    ASSERT_SAME_TYPE(char*,         decltype(strcpy(cp, cpc)));
-    ASSERT_SAME_TYPE(char*,         decltype(strncpy(cp, cpc, s)));
-    ASSERT_SAME_TYPE(char*,         decltype(strcat(cp, cpc)));
-    ASSERT_SAME_TYPE(char*,         decltype(strncat(cp, cpc, s)));
-    ASSERT_SAME_TYPE(int,           decltype(memcmp(vpc, vpc, s)));
-    ASSERT_SAME_TYPE(int,           decltype(strcmp(cpc, cpc)));
-    ASSERT_SAME_TYPE(int,           decltype(strncmp(cpc, cpc, s)));
-    ASSERT_SAME_TYPE(int,           decltype(strcoll(cpc, cpc)));
-    ASSERT_SAME_TYPE(size_t,        decltype(strxfrm(cp, cpc, s)));
-    ASSERT_SAME_TYPE(void*,         decltype(memchr(vp, 0, s)));
-    ASSERT_SAME_TYPE(const void*,   decltype(memchr(vpc, 0, s)));
-    ASSERT_SAME_TYPE(char*,         decltype(strchr(cp, 0)));
-    ASSERT_SAME_TYPE(const char*,   decltype(strchr(cpc, 0)));
-    ASSERT_SAME_TYPE(size_t,        decltype(strcspn(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,         decltype(strpbrk(cp, cpc)));
-    ASSERT_SAME_TYPE(const char*,   decltype(strpbrk(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,         decltype(strrchr(cp, 0)));
-    ASSERT_SAME_TYPE(const char*,   decltype(strrchr(cpc, 0)));
-    ASSERT_SAME_TYPE(size_t,        decltype(strspn(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,         decltype(strstr(cp, cpc)));
-    ASSERT_SAME_TYPE(const char*,   decltype(strstr(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,         decltype(strtok(cp, cpc)));
-    ASSERT_SAME_TYPE(void*,         decltype(memset(vp, 0, s)));
-    ASSERT_SAME_TYPE(char*,         decltype(strerror(0)));
-    ASSERT_SAME_TYPE(size_t,        decltype(strlen(cpc)));
+    // Functions we get directly from the C library (just check the signature)
+    {
+        size_t s = 0;
+        void* vp = 0;
+        const void* vpc = 0;
+        char* cp = 0;
+        const char* cpc = 0;
+        ASSERT_SAME_TYPE(void*,         decltype(memcpy(vp, vpc, s)));
+        ASSERT_SAME_TYPE(void*,         decltype(memmove(vp, vpc, s)));
+        ASSERT_SAME_TYPE(char*,         decltype(strcpy(cp, cpc)));
+        ASSERT_SAME_TYPE(char*,         decltype(strncpy(cp, cpc, s)));
+        ASSERT_SAME_TYPE(char*,         decltype(strcat(cp, cpc)));
+        ASSERT_SAME_TYPE(char*,         decltype(strncat(cp, cpc, s)));
+        ASSERT_SAME_TYPE(int,           decltype(memcmp(vpc, vpc, s)));
+        ASSERT_SAME_TYPE(int,           decltype(strcmp(cpc, cpc)));
+        ASSERT_SAME_TYPE(int,           decltype(strncmp(cpc, cpc, s)));
+        ASSERT_SAME_TYPE(int,           decltype(strcoll(cpc, cpc)));
+        ASSERT_SAME_TYPE(size_t,        decltype(strxfrm(cp, cpc, s)));
+        ASSERT_SAME_TYPE(size_t,        decltype(strcspn(cpc, cpc)));
+        ASSERT_SAME_TYPE(size_t,        decltype(strspn(cpc, cpc)));
+        ASSERT_SAME_TYPE(char*,         decltype(strtok(cp, cpc)));
+        ASSERT_SAME_TYPE(void*,         decltype(memset(vp, 0, s)));
+        ASSERT_SAME_TYPE(char*,         decltype(strerror(0)));
+        ASSERT_SAME_TYPE(size_t,        decltype(strlen(cpc)));
+    }
+
+    // Functions we (may) reimplement
+    {
+        // const char* strchr(const char*, int)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(strchr(s, 'l')));
+        const char* res = strchr(s, 'l');
+        assert(res == &s[2]);
+    }
+    {
+        // char* strchr(char*, int)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(strchr(s, 'l')));
+        char* res = strchr(s, 'l');
+        assert(res == &s[2]);
+    }
+
+    {
+        // const char* strpbrk(const char*, const char*)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(strpbrk(s, "el")));
+        const char* res = strpbrk(s, "el");
+        assert(res == &s[1]);
+    }
+    {
+        // char* strpbrk(char*, const char*)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(strpbrk(s, "el")));
+        char* res = strpbrk(s, "el");
+        assert(res == &s[1]);
+    }
+
+    {
+        // const char* strrchr(const char*, int)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(strrchr(s, 'l')));
+        const char* res = strrchr(s, 'l');
+        assert(res == &s[9]);
+    }
+    {
+        // char* strrchr(char*, int)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(strrchr(s, 'l')));
+        char* res = strrchr(s, 'l');
+        assert(res == &s[9]);
+    }
+
+    {
+        // const void* memchr(const void*, int, size_t)
+        char storage[] = "hello world";
+        size_t count = 11;
+        const void* s = storage;
+        ASSERT_SAME_TYPE(const void*, decltype(memchr(s, 'l', count)));
+        const void* res = memchr(s, 'l', count);
+        assert(res == &storage[2]);
+    }
+    {
+        // void* memchr(void*, int, size_t)
+        char storage[] = "hello world";
+        size_t count = 11;
+        void* s = storage;
+        ASSERT_SAME_TYPE(void*, decltype(memchr(s, 'l', count)));
+        void* res = memchr(s, 'l', count);
+        assert(res == &storage[2]);
+    }
+
+    {
+        // const char* strstr(const char*, const char*)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(strstr(s, "wor")));
+        const char* res = strstr(s, "wor");
+        assert(res == &storage[6]);
+    }
+    {
+        // char* strstr(char*, const char*)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(strstr(s, "wor")));
+        char* res = strstr(s, "wor");
+        assert(res == &storage[6]);
+    }
 
     return 0;
 }
diff --git a/libcxx/test/std/strings/c.strings/cstring.pass.cpp b/libcxx/test/std/strings/c.strings/cstring.pass.cpp
--- a/libcxx/test/std/strings/c.strings/cstring.pass.cpp
+++ b/libcxx/test/std/strings/c.strings/cstring.pass.cpp
@@ -9,6 +9,7 @@
 // <cstring>
 
 #include <cstring>
+#include <cassert>
 #include <type_traits>
 
 #include "test_macros.h"
@@ -19,39 +20,119 @@
 
 int main(int, char**)
 {
-    std::size_t s = 0;
-    void* vp = 0;
-    const void* vpc = 0;
-    char* cp = 0;
-    const char* cpc = 0;
-
-    ASSERT_SAME_TYPE(void*,       decltype(std::memcpy(vp, vpc, s)));
-    ASSERT_SAME_TYPE(void*,       decltype(std::memmove(vp, vpc, s)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strcpy(cp, cpc)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strncpy(cp, cpc, s)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strcat(cp, cpc)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strncat(cp, cpc, s)));
-    ASSERT_SAME_TYPE(int,         decltype(std::memcmp(vpc, vpc, s)));
-    ASSERT_SAME_TYPE(int,         decltype(std::strcmp(cpc, cpc)));
-    ASSERT_SAME_TYPE(int,         decltype(std::strncmp(cpc, cpc, s)));
-    ASSERT_SAME_TYPE(int,         decltype(std::strcoll(cpc, cpc)));
-    ASSERT_SAME_TYPE(std::size_t, decltype(std::strxfrm(cp, cpc, s)));
-    ASSERT_SAME_TYPE(void*,       decltype(std::memchr(vp, 0, s)));
-    ASSERT_SAME_TYPE(const void*, decltype(std::memchr(vpc, 0, s)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strchr(cp, 0)));
-    ASSERT_SAME_TYPE(const char*, decltype(std::strchr(cpc, 0)));
-    ASSERT_SAME_TYPE(std::size_t, decltype(std::strcspn(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strpbrk(cp, cpc)));
-    ASSERT_SAME_TYPE(const char*, decltype(std::strpbrk(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strrchr(cp, 0)));
-    ASSERT_SAME_TYPE(const char*, decltype(std::strrchr(cpc, 0)));
-    ASSERT_SAME_TYPE(std::size_t, decltype(std::strspn(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strstr(cp, cpc)));
-    ASSERT_SAME_TYPE(const char*, decltype(std::strstr(cpc, cpc)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strtok(cp, cpc)));
-    ASSERT_SAME_TYPE(void*,       decltype(std::memset(vp, 0, s)));
-    ASSERT_SAME_TYPE(char*,       decltype(std::strerror(0)));
-    ASSERT_SAME_TYPE(std::size_t, decltype(std::strlen(cpc)));
+    // Functions we get directly from the C library (just check the signature)
+    {
+        std::size_t s = 0;
+        void* vp = 0;
+        const void* vpc = 0;
+        char* cp = 0;
+        const char* cpc = 0;
+        ASSERT_SAME_TYPE(void*,         decltype(std::memcpy(vp, vpc, s)));
+        ASSERT_SAME_TYPE(void*,         decltype(std::memmove(vp, vpc, s)));
+        ASSERT_SAME_TYPE(char*,         decltype(std::strcpy(cp, cpc)));
+        ASSERT_SAME_TYPE(char*,         decltype(std::strncpy(cp, cpc, s)));
+        ASSERT_SAME_TYPE(char*,         decltype(std::strcat(cp, cpc)));
+        ASSERT_SAME_TYPE(char*,         decltype(std::strncat(cp, cpc, s)));
+        ASSERT_SAME_TYPE(int,           decltype(std::memcmp(vpc, vpc, s)));
+        ASSERT_SAME_TYPE(int,           decltype(std::strcmp(cpc, cpc)));
+        ASSERT_SAME_TYPE(int,           decltype(std::strncmp(cpc, cpc, s)));
+        ASSERT_SAME_TYPE(int,           decltype(std::strcoll(cpc, cpc)));
+        ASSERT_SAME_TYPE(std::size_t,   decltype(std::strxfrm(cp, cpc, s)));
+        ASSERT_SAME_TYPE(std::size_t,   decltype(std::strcspn(cpc, cpc)));
+        ASSERT_SAME_TYPE(std::size_t,   decltype(std::strspn(cpc, cpc)));
+        ASSERT_SAME_TYPE(char*,         decltype(std::strtok(cp, cpc)));
+        ASSERT_SAME_TYPE(void*,         decltype(std::memset(vp, 0, s)));
+        ASSERT_SAME_TYPE(char*,         decltype(std::strerror(0)));
+        ASSERT_SAME_TYPE(std::size_t,   decltype(std::strlen(cpc)));
+    }
+
+    // Functions we (may) reimplement
+    {
+        // const char* strchr(const char*, int)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(std::strchr(s, 'l')));
+        const char* res = std::strchr(s, 'l');
+        assert(res == &s[2]);
+    }
+    {
+        // char* strchr(char*, int)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(std::strchr(s, 'l')));
+        char* res = std::strchr(s, 'l');
+        assert(res == &s[2]);
+    }
+
+    {
+        // const char* strpbrk(const char*, const char*)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(std::strpbrk(s, "el")));
+        const char* res = std::strpbrk(s, "el");
+        assert(res == &s[1]);
+    }
+    {
+        // char* strpbrk(char*, const char*)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(std::strpbrk(s, "el")));
+        char* res = std::strpbrk(s, "el");
+        assert(res == &s[1]);
+    }
+
+    {
+        // const char* strrchr(const char*, int)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(std::strrchr(s, 'l')));
+        const char* res = std::strrchr(s, 'l');
+        assert(res == &s[9]);
+    }
+    {
+        // char* strrchr(char*, int)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(std::strrchr(s, 'l')));
+        char* res = std::strrchr(s, 'l');
+        assert(res == &s[9]);
+    }
+
+    {
+        // const void* memchr(const void*, int, size_t)
+        char storage[] = "hello world";
+        std::size_t count = 11;
+        const void* s = storage;
+        ASSERT_SAME_TYPE(const void*, decltype(std::memchr(s, 'l', count)));
+        const void* res = std::memchr(s, 'l', count);
+        assert(res == &storage[2]);
+    }
+    {
+        // void* memchr(void*, int, size_t)
+        char storage[] = "hello world";
+        std::size_t count = 11;
+        void* s = storage;
+        ASSERT_SAME_TYPE(void*, decltype(std::memchr(s, 'l', count)));
+        void* res = std::memchr(s, 'l', count);
+        assert(res == &storage[2]);
+    }
+
+    {
+        // const char* strstr(const char*, const char*)
+        char storage[] = "hello world";
+        const char* s = storage;
+        ASSERT_SAME_TYPE(const char*, decltype(std::strstr(s, "wor")));
+        const char* res = std::strstr(s, "wor");
+        assert(res == &storage[6]);
+    }
+    {
+        // char* strstr(char*, const char*)
+        char storage[] = "hello world";
+        char* s = storage;
+        ASSERT_SAME_TYPE(char*, decltype(std::strstr(s, "wor")));
+        char* res = std::strstr(s, "wor");
+        assert(res == &storage[6]);
+    }
 
     return 0;
 }