[constexpr] Support for constant evaluation of __builtin_memcpy and

__builtin_memmove (in non-type-punning cases).

This is intended to permit libc++ to make std::copy etc constexpr
without sacrificing the optimization that uses memcpy on
trivially-copyable types.

__builtin_strcpy and __builtin_wcscpy are not handled by this change.
They'd be straightforward to add, but we haven't encountered a need for
them just yet.

This reinstates r338455, reverted in r338602, with a fix to avoid trying
to constant-evaluate a memcpy call if either pointer operand has an
invalid designator.

llvm-svn: 338941

1 files changed, 199 insertions, 48 deletions

diff --git a/clang/lib/AST/ExprConstant.cpp b/clang/lib/AST/ExprConstant.cpp
index 25817b475c3..222ff74aaac 100644
--- a/clang/lib/AST/ExprConstant.cpp
+++ b/clang/lib/AST/ExprConstant.cpp
@@ -319,6 +319,25 @@ namespace {
       return false;
     }
 
+    /// Get the range of valid index adjustments in the form
+    ///   {maximum value that can be subtracted from this pointer,
+    ///    maximum value that can be added to this pointer}
+    std::pair<uint64_t, uint64_t> validIndexAdjustments() {
+      if (Invalid || isMostDerivedAnUnsizedArray())
+        return {0, 0};
+
+      // [expr.add]p4: For the purposes of these operators, a pointer to a
+      // nonarray object behaves the same as a pointer to the first element of
+      // an array of length one with the type of the object as its element type.
+      bool IsArray = MostDerivedPathLength == Entries.size() &&
+                     MostDerivedIsArrayElement;
+      uint64_t ArrayIndex =
+          IsArray ? Entries.back().ArrayIndex : (uint64_t)IsOnePastTheEnd;
+      uint64_t ArraySize =
+          IsArray ? getMostDerivedArraySize() : (uint64_t)1;
+      return {ArrayIndex, ArraySize - ArrayIndex};
+    }
+
     /// Check that this refers to a valid subobject.
     bool isValidSubobject() const {
       if (Invalid)
@@ -329,6 +348,14 @@ namespace {
     /// relevant diagnostic and set the designator as invalid.
     bool checkSubobject(EvalInfo &Info, const Expr *E, CheckSubobjectKind CSK);
 
+    /// Get the type of the designated object.
+    QualType getType(ASTContext &Ctx) const {
+      assert(!Invalid && "invalid designator has no subobject type");
+      return MostDerivedPathLength == Entries.size()
+                 ? MostDerivedType
+                 : Ctx.getRecordType(getAsBaseClass(Entries.back()));
+    }
+
     /// Update this designator to refer to the first element within this array.
     void addArrayUnchecked(const ConstantArrayType *CAT) {
       PathEntry Entry;
@@ -1706,6 +1733,54 @@ static bool IsGlobalLValue(APValue::LValueBase B) {
   }
 }
 
+static const ValueDecl *GetLValueBaseDecl(const LValue &LVal) {
+  return LVal.Base.dyn_cast<const ValueDecl*>();
+}
+
+static bool IsLiteralLValue(const LValue &Value) {
+  if (Value.getLValueCallIndex())
+    return false;
+  const Expr *E = Value.Base.dyn_cast<const Expr*>();
+  return E && !isa<MaterializeTemporaryExpr>(E);
+}
+
+static bool IsWeakLValue(const LValue &Value) {
+  const ValueDecl *Decl = GetLValueBaseDecl(Value);
+  return Decl && Decl->isWeak();
+}
+
+static bool isZeroSized(const LValue &Value) {
+  const ValueDecl *Decl = GetLValueBaseDecl(Value);
+  if (Decl && isa<VarDecl>(Decl)) {
+    QualType Ty = Decl->getType();
+    if (Ty->isArrayType())
+      return Ty->isIncompleteType() ||
+             Decl->getASTContext().getTypeSize(Ty) == 0;
+  }
+  return false;
+}
+
+static bool HasSameBase(const LValue &A, const LValue &B) {
+  if (!A.getLValueBase())
+    return !B.getLValueBase();
+  if (!B.getLValueBase())
+    return false;
+
+  if (A.getLValueBase().getOpaqueValue() !=
+      B.getLValueBase().getOpaqueValue()) {
+    const Decl *ADecl = GetLValueBaseDecl(A);
+    if (!ADecl)
+      return false;
+    const Decl *BDecl = GetLValueBaseDecl(B);
+    if (!BDecl || ADecl->getCanonicalDecl() != BDecl->getCanonicalDecl())
+      return false;
+  }
+
+  return IsGlobalLValue(A.getLValueBase()) ||
+         (A.getLValueCallIndex() == B.getLValueCallIndex() &&
+          A.getLValueVersion() == B.getLValueVersion());
+}
+
 static void NoteLValueLocation(EvalInfo &Info, APValue::LValueBase Base) {
   assert(Base && "no location for a null lvalue");
   const ValueDecl *VD = Base.dyn_cast<const ValueDecl*>();
@@ -1917,33 +1992,6 @@ CheckConstantExpression(EvalInfo &Info, SourceLocation DiagLoc, QualType Type,
   return true;
 }
 
-static const ValueDecl *GetLValueBaseDecl(const LValue &LVal) {
-  return LVal.Base.dyn_cast<const ValueDecl*>();
-}
-
-static bool IsLiteralLValue(const LValue &Value) {
-  if (Value.getLValueCallIndex())
-    return false;
-  const Expr *E = Value.Base.dyn_cast<const Expr*>();
-  return E && !isa<MaterializeTemporaryExpr>(E);
-}
-
-static bool IsWeakLValue(const LValue &Value) {
-  const ValueDecl *Decl = GetLValueBaseDecl(Value);
-  return Decl && Decl->isWeak();
-}
-
-static bool isZeroSized(const LValue &Value) {
-  const ValueDecl *Decl = GetLValueBaseDecl(Value);
-  if (Decl && isa<VarDecl>(Decl)) {
-    QualType Ty = Decl->getType();
-    if (Ty->isArrayType())
-      return Ty->isIncompleteType() ||
-             Decl->getASTContext().getTypeSize(Ty) == 0;
-  }
-  return false;
-}
-
 static bool EvalPointerValueAsBool(const APValue &Value, bool &Result) {
   // A null base expression indicates a null pointer.  These are always
   // evaluatable, and they are false unless the offset is zero.
@@ -6117,6 +6165,130 @@ bool PointerExprEvaluator::VisitBuiltinCallExpr(const CallExpr *E,
     return ZeroInitialization(E);
   }
 
+  case Builtin::BImemcpy:
+  case Builtin::BImemmove:
+  case Builtin::BIwmemcpy:
+  case Builtin::BIwmemmove:
+    if (Info.getLangOpts().CPlusPlus11)
+      Info.CCEDiag(E, diag::note_constexpr_invalid_function)
+        << /*isConstexpr*/0 << /*isConstructor*/0
+        << (std::string("'") + Info.Ctx.BuiltinInfo.getName(BuiltinOp) + "'");
+    else
+      Info.CCEDiag(E, diag::note_invalid_subexpr_in_const_expr);
+    LLVM_FALLTHROUGH;
+  case Builtin::BI__builtin_memcpy:
+  case Builtin::BI__builtin_memmove:
+  case Builtin::BI__builtin_wmemcpy:
+  case Builtin::BI__builtin_wmemmove: {
+    bool WChar = BuiltinOp == Builtin::BIwmemcpy ||
+                 BuiltinOp == Builtin::BIwmemmove ||
+                 BuiltinOp == Builtin::BI__builtin_wmemcpy ||
+                 BuiltinOp == Builtin::BI__builtin_wmemmove;
+    bool Move = BuiltinOp == Builtin::BImemmove ||
+                BuiltinOp == Builtin::BIwmemmove ||
+                BuiltinOp == Builtin::BI__builtin_memmove ||
+                BuiltinOp == Builtin::BI__builtin_wmemmove;
+
+    // The result of mem* is the first argument.
+    if (!Visit(E->getArg(0)) || Result.Designator.Invalid)
+      return false;
+    LValue Dest = Result;
+
+    LValue Src;
+    if (!EvaluatePointer(E->getArg(1), Src, Info) || Src.Designator.Invalid)
+      return false;
+
+    APSInt N;
+    if (!EvaluateInteger(E->getArg(2), N, Info))
+      return false;
+    assert(!N.isSigned() && "memcpy and friends take an unsigned size");
+
+    // If the size is zero, we treat this as always being a valid no-op.
+    // (Even if one of the src and dest pointers is null.)
+    if (!N)
+      return true;
+
+    // We require that Src and Dest are both pointers to arrays of
+    // trivially-copyable type. (For the wide version, the designator will be
+    // invalid if the designated object is not a wchar_t.)
+    QualType T = Dest.Designator.getType(Info.Ctx);
+    QualType SrcT = Src.Designator.getType(Info.Ctx);
+    if (!Info.Ctx.hasSameUnqualifiedType(T, SrcT)) {
+      Info.FFDiag(E, diag::note_constexpr_memcpy_type_pun) << Move << SrcT << T;
+      return false;
+    }
+    if (!T.isTriviallyCopyableType(Info.Ctx)) {
+      Info.FFDiag(E, diag::note_constexpr_memcpy_nontrivial) << Move << T;
+      return false;
+    }
+
+    // Figure out how many T's we're copying.
+    uint64_t TSize = Info.Ctx.getTypeSizeInChars(T).getQuantity();
+    if (!WChar) {
+      uint64_t Remainder;
+      llvm::APInt OrigN = N;
+      llvm::APInt::udivrem(OrigN, TSize, N, Remainder);
+      if (Remainder) {
+        Info.FFDiag(E, diag::note_constexpr_memcpy_unsupported)
+            << Move << WChar << 0 << T << OrigN.toString(10, /*Signed*/false)
+            << (unsigned)TSize;
+        return false;
+      }
+    }
+
+    // Check that the copying will remain within the arrays, just so that we
+    // can give a more meaningful diagnostic. This implicitly also checks that
+    // N fits into 64 bits.
+    uint64_t RemainingSrcSize = Src.Designator.validIndexAdjustments().second;
+    uint64_t RemainingDestSize = Dest.Designator.validIndexAdjustments().second;
+    if (N.ugt(RemainingSrcSize) || N.ugt(RemainingDestSize)) {
+      Info.FFDiag(E, diag::note_constexpr_memcpy_unsupported)
+          << Move << WChar << (N.ugt(RemainingSrcSize) ? 1 : 2) << T
+          << N.toString(10, /*Signed*/false);
+      return false;
+    }
+    uint64_t NElems = N.getZExtValue();
+    uint64_t NBytes = NElems * TSize;
+
+    // Check for overlap.
+    int Direction = 1;
+    if (HasSameBase(Src, Dest)) {
+      uint64_t SrcOffset = Src.getLValueOffset().getQuantity();
+      uint64_t DestOffset = Dest.getLValueOffset().getQuantity();
+      if (DestOffset >= SrcOffset && DestOffset - SrcOffset < NBytes) {
+        // Dest is inside the source region.
+        if (!Move) {
+          Info.FFDiag(E, diag::note_constexpr_memcpy_overlap) << WChar;
+          return false;
+        }
+        // For memmove and friends, copy backwards.
+        if (!HandleLValueArrayAdjustment(Info, E, Src, T, NElems - 1) ||
+            !HandleLValueArrayAdjustment(Info, E, Dest, T, NElems - 1))
+          return false;
+        Direction = -1;
+      } else if (!Move && SrcOffset >= DestOffset &&
+                 SrcOffset - DestOffset < NBytes) {
+        // Src is inside the destination region for memcpy: invalid.
+        Info.FFDiag(E, diag::note_constexpr_memcpy_overlap) << WChar;
+        return false;
+      }
+    }
+
+    while (true) {
+      APValue Val;
+      if (!handleLValueToRValueConversion(Info, E, T, Src, Val) ||
+          !handleAssignment(Info, E, Dest, T, Val))
+        return false;
+      // Do not iterate past the last element; if we're copying backwards, that
+      // might take us off the start of the array.
+      if (--NElems == 0)
+        return true;
+      if (!HandleLValueArrayAdjustment(Info, E, Src, T, Direction) ||
+          !HandleLValueArrayAdjustment(Info, E, Dest, T, Direction))
+        return false;
+    }
+  }
+
   default:
     return visitNonBuiltinCallExpr(E);
   }
@@ -8357,27 +8529,6 @@ bool IntExprEvaluator::VisitBuiltinCallExpr(const CallExpr *E,
   }
 }
 
-static bool HasSameBase(const LValue &A, const LValue &B) {
-  if (!A.getLValueBase())
-    return !B.getLValueBase();
-  if (!B.getLValueBase())
-    return false;
-
-  if (A.getLValueBase().getOpaqueValue() !=
-      B.getLValueBase().getOpaqueValue()) {
-    const Decl *ADecl = GetLValueBaseDecl(A);
-    if (!ADecl)
-      return false;
-    const Decl *BDecl = GetLValueBaseDecl(B);
-    if (!BDecl || ADecl->getCanonicalDecl() != BDecl->getCanonicalDecl())
-      return false;
-  }
-
-  return IsGlobalLValue(A.getLValueBase()) ||
-         (A.getLValueCallIndex() == B.getLValueCallIndex() &&
-          A.getLValueVersion() == B.getLValueVersion());
-}
-
 /// Determine whether this is a pointer past the end of the complete
 /// object referred to by the lvalue.
 static bool isOnePastTheEndOfCompleteObject(const ASTContext &Ctx,