[ExprConstant] Improve memchr/memcmp for type mismatch and multibyte element types

[hubert.reinterpretcast]

Summary

memchr and memcmp operate upon the character units of the object representation; that is, the size_t parameter expresses the number of character units. The constant folding implementation is updated in this patch to account for multibyte element types in the arrays passed to memchr/memcmp and, in the case of memcmp, to account for the possibility that the arrays may have differing element types (even when they are byte-sized).

Actual inspection of the object representation is not implemented. Comparisons are done only between elements with the same object size; that is, memchr will fail when inspecting at least one character unit of a multibyte element. The integer types are assumed to have two's complement representation with 0 for false, 1 for true, and no padding bits.

memcmp on multibyte elements will only be able to fold in cases where enough elements are equal for the answer to be 0.

Various tests are added to guard against incorrect folding for cases that miscompile on some system or other prior to this patch. At the same time, the unsigned 32-bit wchar_t testing in test/SemaCXX/constexpr-string.cpp is restored.

[aaron.ballman]

lib/AST/ExprConstant.cpp

6151

Drop the top-level const.

8452

Drop top-level const. (Same suggestion anywhere the type is local to a function and is not a pointer or reference type.)

8465

Don't use auto here as the type is not spelled out in the initialization.

8469

Drop const and use a non-deduced type.

8470

Can you add a string literal to this assert explaining what's gone wrong if it triggers?

[rsmith]

lib/AST/ExprConstant.cpp

6147–6148

Why do we need to do this explicitly, rather than allowing to simply happen as part of the first handleLValueToRValueConversion below?

6150

Considering the LValue base here is incorrect. The object or array we're copying could be a subobject, and the complete object type (the type of the lvalue base) is irrelevant for such copies. Use Result.Designator.getType(Info.Ctx) to find the type that the lvalue designates. (You can bail out here if the designator is invalid; handleLValueToRValueConversion will always fail on such cases anyway.

6159–6160

Please add an assert here that the types do match in the non-raw-byte case. (They must, or the subobject designator would be invalid; the only special case is that a void* can point to anything, and only the memchr variants here take a void*.)

8437–8440

Per above comment, this is not correct.

8471

Style nit: please use while (true) rather than for (;;)

8475–8480

The *only* possible problem here is for bool, right? This comment would be clearer if it said that.

8488

Please add a comment before this return indicating that the result depends on byte order (and maybe a FIXME to compare the bytes in the right order rather than bailing out). We're going to need to deal with the byte order / representation problem for std::bit_cast pretty soon anyway.

8492–8493

This looks wrong. If 0 < MaxLength && MaxLength < LengthPerElement, we're supposed to compare *part of* the next element; this current approach doesn't do that. (If you did one more full-element compare, that'd be conservatively correct because we're only checking for equality, not ordering, but perhaps we should only permit cases where MaxLength is a multiple of LengthPerElement?

test/CodeGenCXX/builtins.cpp

41 ↗

(On Diff #177498)

Please test this in a way that doesn't rely on IR generation constant-evaluating if conditions. Moreover, there's nothing about IR generation that you're actually testing here, so please phrase this as a Sema test instead (eg, check that a VLA bound gets folded to a constant). Likewise for the other tests below.

[hubert.reinterpretcast]

Make an initial pass at addressing the review comments

Address comments on style and code comments

lib/AST/ExprConstant.cpp

6159–6160

Will do.

8475–8480

We do assume two's complement representation (which C89 does not require to be true); so, bool is more problematic than other things, but the comment is not just about bool.

8492–8493

We are doing one more full-element compare to be conservatively correct. There is a test for that.

test/CodeGenCXX/builtins.cpp

41 ↗

(On Diff #177498)

Not all of these cases can fold successfully with the current implementation. The check would need to be that we either fold (and get the right value), or don't fold at all.

[rsmith]

lib/AST/ExprConstant.cpp

8469

Use toCharUnitsFromBits here, and use CharUnits as a type-safe way of representing a size in terms of a number of chars. In fact, consider using getTypeSizeInChars a few lines above and only operating in chars, never bits.

8475–8480

There is no type other than bool that needs the extOrTrunc; maybe drop the "especially"?

8492–8493

Oh, I see now. Right. :)

Maybe add "Be careful not to compare more than MaxLength bytes" to the FIXME above, so a future maintainer doesn't get confused?

test/CodeGenCXX/builtins.cpp

41 ↗

(On Diff #177498)

Seems fine to have a test that we don't fold certain cases at all, with a comment saying that it's OK if we start folding them to a constant and what that constant should be.

Generally the principle is that we want our unit tests to test as few layers of the stack as possible; the chosen test directory should ideally correspond to the layer under test. If you'd really like this to be more of an integration test, that's fine too (eg, if you have code like this in a platform header that really must be handled a certain way), but then it would belong in test/Integration. If you do put it in test/Integration, it'd then be reasonable to include -O in the test flags too, if that makes sense for what you want to test.

[hubert.reinterpretcast]

Use lvalue designator, add assertions for type matching

[hubert.reinterpretcast]

lib/AST/ExprConstant.cpp

6147–6148

We want the error message to be produced even if we bail early on not having a valid designator.

6150

Got it; I also updated the tests to be sensitive to this issue.

test/CodeGenCXX/builtins.cpp

41 ↗

(On Diff #177498)

I think a SemaCXX test based on the following pattern would work:

constexpr decltype(sizeof 0) Good = 42, Bad = 43;
template <decltype(sizeof 0)> struct A;
struct NotBad {};
template <> struct A<Good> : NotBad {};

template <typename T, decltype(sizeof 0) N> A<N> *evalFor(T (&)[N]);
NotBad *evalFor(...);
void chk(NotBad *);

void f() {
  int x[__builtin_memcmp("", "", 1) == 0 ? Good : Bad];
  chk(evalFor(x));
}

[hubert.reinterpretcast]

Address remaining ExprConstant.cpp review comments

Use BytesRemaining/BytesPerElement to improve readability;
tweak FIXME comment to refer to the _remaining_ bytes.
Use CharUnits-to-CharUnits comparisons where straightforward.
Tweak comment about internal representation mismatch.

[hubert.reinterpretcast]

I'll update the tests to be in terms of constant/variable array length tomorrow. I think I've gotten through the rest of the comments.

[hubert.reinterpretcast]

Recast representation-sensitive tests as SemaCXX tests using array bounds

[rsmith]

lib/AST/ExprConstant.cpp

6147–6148

If we have an invalid designator, we already produced a diagnostic when setting it invalid, and generally don't need to diagnose anything else.

[hubert.reinterpretcast]

lib/AST/ExprConstant.cpp

6147–6148

The null pointer diagnostic does not get produced if we do not do the check here on cases like the following:

static_assert(__builtin_memchr((int *)0, 0, 1) == 0, "");

include/clang/Basic/DiagnosticASTKinds.td

def note_constexpr_access_volatile_obj : Note<
   "%select{temporary|object %2|member %2}1 is not allowed in "
   "a constant expression">;
 def note_constexpr_ltor_mutable : Note<
   "read of mutable member %0 is not allowed in a constant expression">;
 def note_constexpr_ltor_non_const_int : Note<
   "read of non-const variable %0 is not allowed in a constant expression">;
 def note_constexpr_ltor_non_constexpr : Note<
   "read of non-constexpr variable %0 is not allowed in a constant expression">;
+def note_constexpr_ltor_incomplete_type : Note<
+  "read of incomplete type %0 is not allowed in a constant expression">;
 def note_constexpr_access_null : Note<
   "%select{read of|assignment to|increment of|decrement of}0 "
   "dereferenced null pointer is not allowed in a constant expression">;
 def note_constexpr_access_past_end : Note<
   "%select{read of|assignment to|increment of|decrement of}0 "
   "dereferenced one-past-the-end pointer is not allowed in a constant expression">;
 def note_constexpr_access_unsized_array : Note<
   "%select{read of|assignment to|increment of|decrement of}0 "

lib/AST/ExprConstant.cpp

for (CallStackFrame *Frame = CurrentCall; Frame != &BottomFrame;
 
     SmallVector<char, 128> Buffer;
     llvm::raw_svector_ostream Out(Buffer);
     describeCall(Frame, Out);
     addDiag(Frame->CallLoc, diag::note_constexpr_call_here) << Out.str();
   }
 }
 
+/// Kinds of access we can perform on an object, for diagnostics.
+enum AccessKinds {
+  AK_Read,
+  AK_Assign,
+  AK_Increment,
+  AK_Decrement
+};
+
 namespace {
   struct ComplexValue {
   private:
     bool IsInt;
 
   public:
     APSInt IntReal, IntImag;
     APFloat FloatReal, FloatImag;
void setNull(QualType PointerTy, uint64_t TargetVal) {
       Designator = SubobjectDesignator(PointerTy->getPointeeType());
       IsNullPtr = true;
     }
 
     void setInvalid(APValue::LValueBase B, unsigned I = 0) {
       set(B, true);
     }
 
+  private:
     // Check that this LValue is not based on a null pointer. If it is, produce
     // a diagnostic and mark the designator as invalid.
-    bool checkNullPointer(EvalInfo &Info, const Expr *E,
-                          CheckSubobjectKind CSK) {
+    template <typename GenDiagType>
+    bool checkNullPointerDiagnosingWith(const GenDiagType &GenDiag) {
       if (Designator.Invalid)
         return false;
       if (IsNullPtr) {
-        Info.CCEDiag(E, diag::note_constexpr_null_subobject)
-          << CSK;
+        GenDiag();
         Designator.setInvalid();
         return false;
       }
       return true;
     }
 
+  public:
+    bool checkNullPointer(EvalInfo &Info, const Expr *E,
+                          CheckSubobjectKind CSK) {
+      return checkNullPointerDiagnosingWith([&Info, E, CSK] {
+        Info.CCEDiag(E, diag::note_constexpr_null_subobject) << CSK;
+      });
+    }
+
+    bool checkNullPointerForFoldAccess(EvalInfo &Info, const Expr *E,
+                                       AccessKinds AK) {
+      return checkNullPointerDiagnosingWith([&Info, E, AK] {
+        Info.FFDiag(E, diag::note_constexpr_access_null) << AK;
+      });
+    }
+
     // Check this LValue refers to an object. If not, set the designator to be
     // invalid and emit a diagnostic.
     bool checkSubobject(EvalInfo &Info, const Expr *E, CheckSubobjectKind CSK) {
       return (CSK == CSK_ArrayToPointer || checkNullPointer(Info, E, CSK)) &&
              Designator.checkSubobject(Info, E, CSK);
     }
 
     void addDecl(EvalInfo &Info, const Expr *E,
static bool diagnoseUnreadableFields(EvalInfo &Info, const Expr *E,
   for (auto &BaseSpec : RD->bases())
     if (diagnoseUnreadableFields(Info, E, BaseSpec.getType()))
       return true;
 
   // All mutable fields were empty, and thus not actually read.
   return false;
 }
 
-/// Kinds of access we can perform on an object, for diagnostics.
-enum AccessKinds {
-  AK_Read,
-  AK_Assign,
-  AK_Increment,
-  AK_Decrement
-};
-
 namespace {
 /// A handle to a complete object (an object that is not a subobject of
 /// another object).
 struct CompleteObject {
   /// The value of the complete object.
   APValue *Value;
   /// The type of the complete object.
   QualType Type;
if (BuiltinOp != Builtin::BIstrchr &&
         BuiltinOp != Builtin::BIwcschr &&
         BuiltinOp != Builtin::BI__builtin_strchr &&
         BuiltinOp != Builtin::BI__builtin_wcschr) {
       APSInt N;
       if (!EvaluateInteger(E->getArg(2), N, Info))
         return false;
       MaxLength = N.getExtValue();
     }
-
-    QualType CharTy = E->getArg(0)->getType()->getPointeeType();
-
+    // We cannot find the value if there are no candidates to match against.
+    if (MaxLength == 0u)
+      return ZeroInitialization(E);
+    if (!Result.checkNullPointerForFoldAccess(Info, E, AK_Read) ||
+        Result.Designator.Invalid)
+      return false;
+    QualType CharTy = Result.Designator.getType(Info.Ctx);
+    bool IsRawByte = BuiltinOp == Builtin::BImemchr ||
+                     BuiltinOp == Builtin::BI__builtin_memchr;
+    assert(IsRawByte ||
+           Info.Ctx.hasSameUnqualifiedType(
+               CharTy, E->getArg(0)->getType()->getPointeeType()));
+    // Pointers to const void may point to objects of incomplete type.
+    if (IsRawByte && CharTy->isIncompleteType()) {
+      Info.FFDiag(E, diag::note_constexpr_ltor_incomplete_type) << CharTy;
+      return false;
+    }
+    // Give up on byte-oriented matching against multibyte elements.
+    // FIXME: We can compare the bytes in the correct order.
+    if (IsRawByte && Info.Ctx.getTypeSizeInChars(CharTy) != CharUnits::One())
+      return false;
     // Figure out what value we're actually looking for (after converting to
     // the corresponding unsigned type if necessary).
     uint64_t DesiredVal;
     bool StopAtNull = false;
     switch (BuiltinOp) {
     case Builtin::BIstrchr:
     case Builtin::BI__builtin_strchr:
       // strchr compares directly to the passed integer, and therefore
bool IntExprEvaluator::VisitBuiltinCallExpr(const CallExpr *E,
   case Builtin::BI__builtin_wcsncmp:
   case Builtin::BI__builtin_memcmp:
   case Builtin::BI__builtin_wmemcmp: {
     LValue String1, String2;
     if (!EvaluatePointer(E->getArg(0), String1, Info) ||
         !EvaluatePointer(E->getArg(1), String2, Info))
       return false;
 
-    QualType CharTy = E->getArg(0)->getType()->getPointeeType();
-
     uint64_t MaxLength = uint64_t(-1);
     if (BuiltinOp != Builtin::BIstrcmp &&
         BuiltinOp != Builtin::BIwcscmp &&
         BuiltinOp != Builtin::BI__builtin_strcmp &&
         BuiltinOp != Builtin::BI__builtin_wcscmp) {
       APSInt N;
       if (!EvaluateInteger(E->getArg(2), N, Info))
         return false;
       MaxLength = N.getExtValue();
     }
+
+    // Empty substrings compare equal by definition.
+    if (MaxLength == 0u)
+      return Success(0, E);
+
+    if (!String1.checkNullPointerForFoldAccess(Info, E, AK_Read) ||
+        !String2.checkNullPointerForFoldAccess(Info, E, AK_Read) ||
+        String1.Designator.Invalid || String2.Designator.Invalid)
+      return false;
+
+    QualType CharTy1 = String1.Designator.getType(Info.Ctx);
+    QualType CharTy2 = String2.Designator.getType(Info.Ctx);
+
+    bool IsRawByte = BuiltinOp == Builtin::BImemcmp ||
+                     BuiltinOp == Builtin::BI__builtin_memcmp;
+
+    assert(IsRawByte ||
+           (Info.Ctx.hasSameUnqualifiedType(
+                CharTy1, E->getArg(0)->getType()->getPointeeType()) &&
+            Info.Ctx.hasSameUnqualifiedType(CharTy1, CharTy2)));
+
+    const auto &ReadCurElems = [&](APValue &Char1, APValue &Char2) {
+      return handleLValueToRValueConversion(Info, E, CharTy1, String1, Char1) &&
+             handleLValueToRValueConversion(Info, E, CharTy2, String2, Char2) &&
+             Char1.isInt() && Char2.isInt();
+    };
+    const auto &AdvanceElems = [&] {
+      return HandleLValueArrayAdjustment(Info, E, String1, CharTy1, 1) &&
+             HandleLValueArrayAdjustment(Info, E, String2, CharTy2, 1);
+    };
+
+    if (IsRawByte) {
+      uint64_t BytesRemaining = MaxLength;
+      // Pointers to const void may point to objects of incomplete type.
+      if (CharTy1->isIncompleteType()) {
+        Info.FFDiag(E, diag::note_constexpr_ltor_incomplete_type) << CharTy1;
+        return false;
+      }
+      if (CharTy2->isIncompleteType()) {
+        Info.FFDiag(E, diag::note_constexpr_ltor_incomplete_type) << CharTy2;
+        return false;
+      }
+      uint64_t CharTy1Width{Info.Ctx.getTypeSize(CharTy1)};
+      CharUnits CharTy1Size = Info.Ctx.toCharUnitsFromBits(CharTy1Width);
+      // Give up on comparing between elements with disparate widths.
+      if (CharTy1Size != Info.Ctx.getTypeSizeInChars(CharTy2))
+        return false;
+      uint64_t BytesPerElement = CharTy1Size.getQuantity();
+      assert(BytesRemaining && "BytesRemaining should not be zero: the "
+                               "following loop considers at least one element");
+      while (true) {
+        APValue Char1, Char2;
+        if (!ReadCurElems(Char1, Char2))
+          return false;
+        // We have compatible in-memory widths, but a possible type and
+        // (for `bool`) internal representation mismatch.
+        // Assuming two's complement representation, including 0 for `false` and
+        // 1 for `true`, we can check an appropriate number of elements for
+        // equality even if they are not byte-sized.
+        APSInt Char1InMem = Char1.getInt().extOrTrunc(CharTy1Width);
+        APSInt Char2InMem = Char2.getInt().extOrTrunc(CharTy1Width);
+        if (Char1InMem.ne(Char2InMem)) {
+          // If the elements are byte-sized, then we can produce a three-way
+          // comparison result in a straightforward manner.
+          if (BytesPerElement == 1u) {
+            // memcmp always compares unsigned chars.
+            return Success(Char1InMem.ult(Char2InMem) ? -1 : 1, E);
+          }
+          // The result is byte-order sensitive, and we have multibyte elements.
+          // FIXME: We can compare the remaining bytes in the correct order.
+          return false;
+        }
+        if (!AdvanceElems())
+          return false;
+        if (BytesRemaining <= BytesPerElement)
+          break;
+        BytesRemaining -= BytesPerElement;
+      }
+      // Enough elements are equal to account for the memcmp limit.
+      return Success(0, E);
+    }
+
     bool StopAtNull = (BuiltinOp != Builtin::BImemcmp &&
                        BuiltinOp != Builtin::BIwmemcmp &&
                        BuiltinOp != Builtin::BI__builtin_memcmp &&
                        BuiltinOp != Builtin::BI__builtin_wmemcmp);
     bool IsWide = BuiltinOp == Builtin::BIwcscmp ||
                   BuiltinOp == Builtin::BIwcsncmp ||
                   BuiltinOp == Builtin::BIwmemcmp ||
                   BuiltinOp == Builtin::BI__builtin_wcscmp ||
                   BuiltinOp == Builtin::BI__builtin_wcsncmp ||
                   BuiltinOp == Builtin::BI__builtin_wmemcmp;
+
     for (; MaxLength; --MaxLength) {
       APValue Char1, Char2;
-      if (!handleLValueToRValueConversion(Info, E, CharTy, String1, Char1) ||
-          !handleLValueToRValueConversion(Info, E, CharTy, String2, Char2) ||
-          !Char1.isInt() || !Char2.isInt())
+      if (!ReadCurElems(Char1, Char2))
         return false;
       if (Char1.getInt() != Char2.getInt()) {
         if (IsWide) // wmemcmp compares with wchar_t signedness.
           return Success(Char1.getInt() < Char2.getInt() ? -1 : 1, E);
         // memcmp always compares unsigned chars.
         return Success(Char1.getInt().ult(Char2.getInt()) ? -1 : 1, E);
       }
       if (StopAtNull && !Char1.getInt())
         return Success(0, E);
       assert(!(StopAtNull && !Char2.getInt()));
-      if (!HandleLValueArrayAdjustment(Info, E, String1, CharTy, 1) ||
-          !HandleLValueArrayAdjustment(Info, E, String2, CharTy, 1))
+      if (!AdvanceElems())
         return false;
     }
     // We hit the strncmp / memcmp limit.
     return Success(0, E);
   }
 
   case Builtin::BI__atomic_always_lock_free:
   case Builtin::BI__atomic_is_lock_free:

test/SemaCXX/constexpr-string.cpp

-// RUN: %clang_cc1 %s -triple x86_64-linux-gnu -std=c++1z -fsyntax-only -verify -pedantic
-// RUN: %clang_cc1 %s -triple x86_64-linux-gnu -std=c++1z -fsyntax-only -verify -pedantic -fno-signed-char
-// RUN: %clang_cc1 %s -triple x86_64-linux-gnu -std=c++1z -fsyntax-only -verify -pedantic -fno-wchar -Dwchar_t=__WCHAR_TYPE__
+// RUN: %clang_cc1 %s -triple x86_64-linux-gnu -std=c++2a -fsyntax-only -verify -pedantic -Wno-vla-extension
+// RUN: %clang_cc1 %s -triple x86_64-linux-gnu -std=c++2a -fsyntax-only -verify -pedantic -Wno-vla-extension -fno-signed-char
+// RUN: %clang_cc1 %s -triple x86_64-linux-gnu -std=c++2a -fsyntax-only -verify -pedantic -Wno-vla-extension -fno-wchar -DNO_PREDEFINED_WCHAR_T
+// RUN: %clang_cc1 %s -triple armebv7-unknown-linux -std=c++2a -fsyntax-only -verify -pedantic -Wno-vla-extension
+// RUN: %clang_cc1 %s -triple armebv7-unknown-linux -std=c++2a -fsyntax-only -verify -pedantic -Wno-vla-extension -fno-signed-char
+// RUN: %clang_cc1 %s -triple armebv7-unknown-linux -std=c++2a -fsyntax-only -verify -pedantic -Wno-vla-extension -fno-wchar -DNO_PREDEFINED_WCHAR_T
 
-# 6 "/usr/include/string.h" 1 3 4
+# 9 "/usr/include/string.h" 1 3 4
 extern "C" {
   typedef decltype(sizeof(int)) size_t;
 
   extern size_t strlen(const char *p);
 
   extern int strcmp(const char *s1, const char *s2);
   extern int strncmp(const char *s1, const char *s2, size_t n);
   extern int memcmp(const void *s1, const void *s2, size_t n);
 
   extern char *strchr(const char *s, int c);
   extern void *memchr(const void *s, int c, size_t n);
 
   extern void *memcpy(void *d, const void *s, size_t n);
   extern void *memmove(void *d, const void *s, size_t n);
 }
-# 22 "SemaCXX/constexpr-string.cpp" 2
+# 25 "SemaCXX/constexpr-string.cpp" 2
 
-# 24 "/usr/include/wchar.h" 1 3 4
+# 27 "/usr/include/wchar.h" 1 3 4
 extern "C" {
+#if NO_PREDEFINED_WCHAR_T
+  typedef decltype(L'0') wchar_t;
+#endif
   extern size_t wcslen(const wchar_t *p);
 
   extern int wcscmp(const wchar_t *s1, const wchar_t *s2);
   extern int wcsncmp(const wchar_t *s1, const wchar_t *s2, size_t n);
   extern int wmemcmp(const wchar_t *s1, const wchar_t *s2, size_t n);
 
   extern wchar_t *wcschr(const wchar_t *s, wchar_t c);
   extern wchar_t *wmemchr(const wchar_t *s, wchar_t c, size_t n);
 
   extern wchar_t *wmemcpy(wchar_t *d, const wchar_t *s, size_t n);
   extern wchar_t *wmemmove(wchar_t *d, const wchar_t *s, size_t n);
 }
 
-# 39 "SemaCXX/constexpr-string.cpp" 2
+# 45 "SemaCXX/constexpr-string.cpp" 2
 namespace Strlen {
   constexpr int n = __builtin_strlen("hello"); // ok
   static_assert(n == 5);
   constexpr int wn = __builtin_wcslen(L"hello"); // ok
   static_assert(wn == 5);
   constexpr int m = strlen("hello"); // expected-error {{constant expression}} expected-note {{non-constexpr function 'strlen' cannot be used in a constant expression}}
   constexpr int wm = wcslen(L"hello"); // expected-error {{constant expression}} expected-note {{non-constexpr function 'wcslen' cannot be used in a constant expression}}
 
namespace StrcmpEtc {
   static_assert(__builtin_memcmp("a\203", "a\003", 2) == 1);
   static_assert(__builtin_memcmp(0, 0, 0) == 0);
   static_assert(__builtin_memcmp("abab\0banana", "abab\0banana", 100) == 0); // expected-error {{not an integral constant}} expected-note {{dereferenced one-past-the-end}}
   static_assert(__builtin_memcmp("abab\0banana", "abab\0canada", 100) == -1); // FIXME: Should we reject this?
   static_assert(__builtin_memcmp("abab\0banana", "abab\0canada", 7) == -1);
   static_assert(__builtin_memcmp("abab\0banana", "abab\0canada", 6) == -1);
   static_assert(__builtin_memcmp("abab\0banana", "abab\0canada", 5) == 0);
 
+  extern struct Incomplete incomplete;
+  static_assert(__builtin_memcmp(&incomplete, "", 0u) == 0);
+  static_assert(__builtin_memcmp("", &incomplete, 0u) == 0);
+  static_assert(__builtin_memcmp(&incomplete, "", 1u) == 42); // expected-error {{not an integral constant}} expected-note {{read of incomplete type 'struct Incomplete'}}
+  static_assert(__builtin_memcmp("", &incomplete, 1u) == 42); // expected-error {{not an integral constant}} expected-note {{read of incomplete type 'struct Incomplete'}}
+
+  constexpr unsigned char ku00fe00[] = {0x00, 0xfe, 0x00};
+  constexpr unsigned char ku00feff[] = {0x00, 0xfe, 0xff};
+  constexpr signed char ks00fe00[] = {0, -2, 0};
+  constexpr signed char ks00feff[] = {0, -2, -1};
+  static_assert(__builtin_memcmp(ku00feff, ks00fe00, 2) == 0);
+  static_assert(__builtin_memcmp(ku00feff, ks00fe00, 99) == 1);
+  static_assert(__builtin_memcmp(ku00fe00, ks00feff, 99) == -1);
+  static_assert(__builtin_memcmp(ks00feff, ku00fe00, 2) == 0);
+  static_assert(__builtin_memcmp(ks00feff, ku00fe00, 99) == 1);
+  static_assert(__builtin_memcmp(ks00fe00, ku00feff, 99) == -1);
+  static_assert(__builtin_memcmp(ks00fe00, ks00feff, 2) == 0);
+  static_assert(__builtin_memcmp(ks00feff, ks00fe00, 99) == 1);
+  static_assert(__builtin_memcmp(ks00fe00, ks00feff, 99) == -1);
+
+  struct Bool3Tuple { bool bb[3]; };
+  constexpr Bool3Tuple kb000100 = {{false, true, false}};
+  static_assert(sizeof(bool) != 1u || __builtin_memcmp(ks00fe00, kb000100.bb, 1) == 0);
+  static_assert(sizeof(bool) != 1u || __builtin_memcmp(ks00fe00, kb000100.bb, 2) == 1);
+
+  constexpr long ksl[] = {0, -1};
+  constexpr unsigned int kui[] = {0, 0u - 1};
+  constexpr unsigned long long kull[] = {0, 0ull - 1};
+  constexpr const auto *kuSizeofLong(void) {
+    if constexpr(sizeof(long) == sizeof(int)) {
+      return kui;
+    } else if constexpr(sizeof(long) == sizeof(long long)) {
+      return kull;
+    } else {
+      return nullptr;
+    }
+  }
+  static_assert(__builtin_memcmp(ksl, kuSizeofLong(), sizeof(long) - 1) == 0);
+  static_assert(__builtin_memcmp(ksl, kuSizeofLong(), sizeof(long) + 0) == 0);
+  static_assert(__builtin_memcmp(ksl, kuSizeofLong(), sizeof(long) + 1) == 0);
+  static_assert(__builtin_memcmp(ksl, kuSizeofLong(), 2*sizeof(long) - 1) == 0);
+  static_assert(__builtin_memcmp(ksl, kuSizeofLong(), 2*sizeof(long) + 0) == 0);
+  static_assert(__builtin_memcmp(ksl, kuSizeofLong(), 2*sizeof(long) + 1) == 42); // expected-error {{not an integral constant}} expected-note {{dereferenced one-past-the-end}}
+  static_assert(__builtin_memcmp(ksl + 1, kuSizeofLong() + 1, sizeof(long) - 1) == 0);
+  static_assert(__builtin_memcmp(ksl + 1, kuSizeofLong() + 1, sizeof(long) + 0) == 0);
+  static_assert(__builtin_memcmp(ksl + 1, kuSizeofLong() + 1, sizeof(long) + 1) == 42); // expected-error {{not an integral constant}} expected-note {{dereferenced one-past-the-end}}
+
   constexpr int a = strcmp("hello", "world"); // expected-error {{constant expression}} expected-note {{non-constexpr function 'strcmp' cannot be used in a constant expression}}
   constexpr int b = strncmp("hello", "world", 3); // expected-error {{constant expression}} expected-note {{non-constexpr function 'strncmp' cannot be used in a constant expression}}
   constexpr int c = memcmp("hello", "world", 3); // expected-error {{constant expression}} expected-note {{non-constexpr function 'memcmp' cannot be used in a constant expression}}
 }
 
+namespace MultibyteElementTests {
+inline namespace Util {
+#define STR2(X) #X
+#define STR(X) STR2(X)
+constexpr const char ByteOrderString[] = STR(__BYTE_ORDER__);
+#undef STR
+#undef STR2
+constexpr bool LittleEndian{*ByteOrderString == '1'};
+
+constexpr size_t GoodFoldArraySize = 42, BadFoldArraySize = 43;
+struct NotBadFoldResult {};
+template <size_t> struct FoldResult;
+template <> struct FoldResult<GoodFoldArraySize> : NotBadFoldResult {};
+template <typename T, size_t N>
+FoldResult<N> *foldResultImpl(T (*ptrToConstantSizeArray)[N]);
+struct NotFolded : NotBadFoldResult {};
+NotFolded *foldResultImpl(bool anyPtr);
+template <auto Value> struct MetaValue;
+template <typename Callable, size_t N, auto ExpectedFoldResult>
+auto foldResult(const Callable &, MetaValue<N> *,
+                MetaValue<ExpectedFoldResult> *) {
+  int (*maybeVLAPtr)[Callable{}(N) == ExpectedFoldResult
+                         ? GoodFoldArraySize
+                         : BadFoldArraySize] = 0;
+  return foldResultImpl(maybeVLAPtr);
+}
+template <typename FoldResultKind, typename Callable, typename NWrap,
+          typename ExpectedWrap>
+constexpr bool checkFoldResult(const Callable &c, NWrap *n, ExpectedWrap *e) {
+  decltype(static_cast<FoldResultKind *>(foldResult(c, n, e))) *chk{};
+  return true;
+}
+template <size_t N> constexpr MetaValue<N> *withN() { return nullptr; }
+template <auto Expected> constexpr MetaValue<Expected> *withExpected() {
+  return nullptr;
+}
+} // namespace Util
+} // namespace MultibyteElementTests
+
+namespace MultibyteElementTests::Memcmp {
+#ifdef __SIZEOF_INT128__
+constexpr __int128 i128_ff_8_00_8 = -(__int128)1 - -1ull;
+constexpr __int128 i128_00_16 = 0;
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memcmp(&i128_ff_8_00_8, &i128_00_16, n);
+    },
+    withN<1u>(), withExpected<LittleEndian ? 0 : 1>()));
+#endif
+
+constexpr const signed char ByteOrderStringReduced[] = {
+    ByteOrderString[0] - '0', ByteOrderString[1] - '0',
+    ByteOrderString[2] - '0', ByteOrderString[3] - '0',
+};
+constexpr signed int i04030201 = 0x04030201;
+constexpr unsigned int u04030201 = 0x04030201u;
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memcmp(ByteOrderStringReduced, &i04030201, n);
+    },
+    withN<sizeof(int)>(), withExpected<0>()));
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memcmp(&u04030201, ByteOrderStringReduced, n);
+    },
+    withN<sizeof(int)>(), withExpected<0>()));
+
+constexpr unsigned int ui0000FEFF = 0x0000feffU;
+constexpr unsigned short usFEFF = 0xfeffU;
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memcmp(&ui0000FEFF, &usFEFF, n);
+    },
+    withN<1u>(), withExpected<LittleEndian ? 0 : -1>()));
+
+constexpr unsigned int ui08038700 = 0x08038700u;
+constexpr unsigned int ui08048600 = 0x08048600u;
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memcmp(&ui08038700, &ui08048600, n);
+    },
+    withN<sizeof(int)>(), withExpected<LittleEndian ? 1 : -1>()));
+}
+
 namespace WcscmpEtc {
   constexpr wchar_t kFoobar[6] = {L'f',L'o',L'o',L'b',L'a',L'r'};
   constexpr wchar_t kFoobazfoobar[12] = {L'f',L'o',L'o',L'b',L'a',L'z',L'f',L'o',L'o',L'b',L'a',L'r'};
 
   static_assert(__builtin_wcscmp(L"abab", L"abab") == 0);
   static_assert(__builtin_wcscmp(L"abab", L"abba") == -1);
   static_assert(__builtin_wcscmp(L"abab", L"abaa") == 1);
   static_assert(__builtin_wcscmp(L"ababa", L"abab") == 1);
namespace StrchrEtc {
   static_assert(__builtin_memchr(kStr, '\xff', 8) == kStr + 4);
   static_assert(__builtin_memchr(kStr, '\xff' + 256, 8) == kStr + 4);
   static_assert(__builtin_memchr(kStr, '\xff' - 256, 8) == kStr + 4);
   static_assert(__builtin_memchr(kFoo, 'x', 3) == nullptr);
   static_assert(__builtin_memchr(kFoo, 'x', 4) == nullptr); // expected-error {{not an integral constant}} expected-note {{dereferenced one-past-the-end}}
   static_assert(__builtin_memchr(nullptr, 'x', 3) == nullptr); // expected-error {{not an integral constant}} expected-note {{dereferenced null}}
   static_assert(__builtin_memchr(nullptr, 'x', 0) == nullptr); // FIXME: Should we reject this?
 
+  extern struct Incomplete incomplete;
+  static_assert(__builtin_memchr(&incomplete, 0, 0u) == nullptr);
+  static_assert(__builtin_memchr(&incomplete, 0, 1u) == nullptr); // expected-error {{not an integral constant}} expected-note {{read of incomplete type 'struct Incomplete'}}
+
+  const unsigned char &u1 = 0xf0;
+  auto &&i1 = (const signed char []){-128}; // expected-warning {{compound literals are a C99-specific feature}}
+  static_assert(__builtin_memchr(&u1, -(0x0f + 1), 1) == &u1);
+  static_assert(__builtin_memchr(i1, 0x80, 1) == i1);
+
+  enum class E : unsigned char {};
+  struct EPair { E e, f; };
+  constexpr EPair ee{E{240}};
+  static_assert(__builtin_memchr(&ee.e, 240, 1) == &ee.e);
+
+  constexpr bool kBool[] = {false, true, false};
+  constexpr const bool *const kBoolPastTheEndPtr = kBool + 3;
+  static_assert(sizeof(bool) != 1u || __builtin_memchr(kBoolPastTheEndPtr - 3, 1, 99) == kBool + 1);
+  static_assert(sizeof(bool) != 1u || __builtin_memchr(kBool + 1, 0, 99) == kBoolPastTheEndPtr - 1);
+  static_assert(sizeof(bool) != 1u || __builtin_memchr(kBoolPastTheEndPtr - 3, -1, 3) == nullptr);
+  static_assert(sizeof(bool) != 1u || __builtin_memchr(kBoolPastTheEndPtr, 0, 1) == nullptr); // expected-error {{not an integral constant}} expected-note {{dereferenced one-past-the-end}}
+
   static_assert(__builtin_char_memchr(kStr, 'a', 0) == nullptr);
   static_assert(__builtin_char_memchr(kStr, 'a', 1) == kStr);
   static_assert(__builtin_char_memchr(kStr, '\0', 5) == nullptr);
   static_assert(__builtin_char_memchr(kStr, '\0', 6) == kStr + 5);
   static_assert(__builtin_char_memchr(kStr, '\xff', 8) == kStr + 4);
   static_assert(__builtin_char_memchr(kStr, '\xff' + 256, 8) == kStr + 4);
   static_assert(__builtin_char_memchr(kStr, '\xff' - 256, 8) == kStr + 4);
   static_assert(__builtin_char_memchr(kFoo, 'x', 3) == nullptr);
constexpr bool char_memchr_mutable() {
     return __builtin_strcmp(buffer, "durable") == 0;
   }
   static_assert(char_memchr_mutable());
 
   constexpr bool a = !strchr("hello", 'h'); // expected-error {{constant expression}} expected-note {{non-constexpr function 'strchr' cannot be used in a constant expression}}
   constexpr bool b = !memchr("hello", 'h', 3); // expected-error {{constant expression}} expected-note {{non-constexpr function 'memchr' cannot be used in a constant expression}}
 }
 
+namespace MultibyteElementTests::Memchr {
+constexpr unsigned int u04030201 = 0x04030201;
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memchr(&u04030201, *ByteOrderString - '0', n);
+    },
+    withN<1u>(), withExpected<&u04030201>()));
+
+constexpr unsigned int uED = 0xEDU;
+static_assert(checkFoldResult<NotBadFoldResult>(
+    [](size_t n) constexpr {
+      return __builtin_memchr(&uED, 0xED, n);
+    },
+    withN<1u>(), withExpected<LittleEndian ? &uED : nullptr>()));
+}
+
 namespace WcschrEtc {
   constexpr const wchar_t *kStr = L"abca\xffff\0dL";
   constexpr wchar_t kFoo[] = {L'f', L'o', L'o'};
   static_assert(__builtin_wcschr(kStr, L'a') == kStr);
   static_assert(__builtin_wcschr(kStr, L'b') == kStr + 1);
   static_assert(__builtin_wcschr(kStr, L'c') == kStr + 2);
   static_assert(__builtin_wcschr(kStr, L'd') == nullptr);
   static_assert(__builtin_wcschr(kStr, L'e') == nullptr);
constexpr int test_memmove(int a, int b, int n) {
     // expected-note@-2 {{source is not a contiguous array of at least 2 elements of type 'int'}}
     // expected-note@-3 {{destination is not a contiguous array of at least 3 elements of type 'int'}}
     return result(arr);
   }
   constexpr int test_wmemcpy(int a, int b, int n) {
     wchar_t arr[4] = {1, 2, 3, 4};
     __builtin_wmemcpy(arr + a, arr + b, n);
     // expected-note@-1 2{{overlapping memory regions}}
-    // expected-note-re@-2 {{source is not a contiguous array of at least 2 elements of type '{{wchar_t|int}}'}}
-    // expected-note-re@-3 {{destination is not a contiguous array of at least 3 elements of type '{{wchar_t|int}}'}}
+    // expected-note@-2 {{source is not a contiguous array of at least 2 elements of type 'wchar_t'}}
+    // expected-note@-3 {{destination is not a contiguous array of at least 3 elements of type 'wchar_t'}}
     return result(arr);
   }
   constexpr int test_wmemmove(int a, int b, int n) {
     wchar_t arr[4] = {1, 2, 3, 4};
     __builtin_wmemmove(arr + a, arr + b, n);
-    // expected-note-re@-1 {{source is not a contiguous array of at least 2 elements of type '{{wchar_t|int}}'}}
-    // expected-note-re@-2 {{destination is not a contiguous array of at least 3 elements of type '{{wchar_t|int}}'}}
+    // expected-note@-1 {{source is not a contiguous array of at least 2 elements of type 'wchar_t'}}
+    // expected-note@-2 {{destination is not a contiguous array of at least 3 elements of type 'wchar_t'}}
     return result(arr);
   }
 
   static_assert(test_memcpy(1, 2, 4) == 1334);
   static_assert(test_memcpy(2, 1, 4) == 1224);
   static_assert(test_memcpy(0, 1, 8) == 2334); // expected-error {{constant}} expected-note {{in call}}
   static_assert(test_memcpy(1, 0, 8) == 1124); // expected-error {{constant}} expected-note {{in call}}
   static_assert(test_memcpy(1, 2, 1) == 1334); // expected-error {{constant}} expected-note {{in call}}