constexpr:

  * support the gcc __builtin_constant_p() ? ... : ... folding hack in C++11
  * check for unspecified values in pointer comparisons and pointer subtractions


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@149578 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 261 insertions, 26 deletions

diff --git a/include/clang/AST/DeclCXX.h b/include/clang/AST/DeclCXX.h
index dcc780781b..f33b762644 100644
--- a/include/clang/AST/DeclCXX.h
+++ b/include/clang/AST/DeclCXX.h
@@ -2774,6 +2774,9 @@ public:
 const DiagnosticBuilder &operator<<(const DiagnosticBuilder &DB,
                                     AccessSpecifier AS);
 
+const PartialDiagnostic &operator<<(const PartialDiagnostic &DB,
+                                    AccessSpecifier AS);
+
 } // end namespace clang
 
 #endif
diff --git a/include/clang/Basic/DiagnosticASTKinds.td b/include/clang/Basic/DiagnosticASTKinds.td
index ba8820a3b0..ce1ca5b038 100644
--- a/include/clang/Basic/DiagnosticASTKinds.td
+++ b/include/clang/Basic/DiagnosticASTKinds.td
@@ -41,6 +41,17 @@ def note_constexpr_float_arithmetic : Note<
 def note_constexpr_pointer_arithmetic : Note<
   "cannot refer to element %0 of non-array object in a constant "
   "expression">;
+def note_constexpr_pointer_subtraction_not_same_array : Note<
+  "subtracted pointers are not elements of the same array">;
+def note_constexpr_pointer_comparison_base_classes : Note<
+  "comparison of addresses of subobjects of different base classes "
+  "has unspecified value">;
+def note_constexpr_pointer_comparison_base_field : Note<
+  "comparison of address of base class subobject %0 of class %1 to field %2 "
+  "has unspecified value">;
+def note_constexpr_pointer_comparison_differing_access : Note<
+  "comparison of address of fields %0 and %2 of %4 with differing access "
+  "specifiers (%1 vs %3) has unspecified value">;
 def note_constexpr_compare_virtual_mem_ptr : Note<
   "comparison of pointer to virtual member function %0 has unspecified value">;
 def note_constexpr_past_end : Note<
diff --git a/lib/AST/DeclCXX.cpp b/lib/AST/DeclCXX.cpp
index 931b7cbf21..d5221031a5 100644
--- a/lib/AST/DeclCXX.cpp
+++ b/lib/AST/DeclCXX.cpp
@@ -1973,3 +1973,8 @@ const DiagnosticBuilder &clang::operator<<(const DiagnosticBuilder &DB,
                                            AccessSpecifier AS) {
   return DB << getAccessName(AS);
 }
+
+const PartialDiagnostic &clang::operator<<(const PartialDiagnostic &DB,
+                                           AccessSpecifier AS) {
+  return DB << getAccessName(AS);
+}
diff --git a/lib/AST/ExprConstant.cpp b/lib/AST/ExprConstant.cpp
index 3209bb343b..a45aea974c 100644
--- a/lib/AST/ExprConstant.cpp
+++ b/lib/AST/ExprConstant.cpp
@@ -78,25 +78,27 @@ namespace {
   }
 
   /// Get an LValue path entry, which is known to not be an array index, as a
-  /// field declaration.
-  const FieldDecl *getAsField(APValue::LValuePathEntry E) {
+  /// field or base class.
+  APValue::BaseOrMemberType getAsBaseOrMember(APValue::LValuePathEntry E) {
     APValue::BaseOrMemberType Value;
     Value.setFromOpaqueValue(E.BaseOrMember);
-    return dyn_cast<FieldDecl>(Value.getPointer());
+    return Value;
+  }
+
+  /// Get an LValue path entry, which is known to not be an array index, as a
+  /// field declaration.
+  const FieldDecl *getAsField(APValue::LValuePathEntry E) {
+    return dyn_cast<FieldDecl>(getAsBaseOrMember(E).getPointer());
   }
   /// Get an LValue path entry, which is known to not be an array index, as a
   /// base class declaration.
   const CXXRecordDecl *getAsBaseClass(APValue::LValuePathEntry E) {
-    APValue::BaseOrMemberType Value;
-    Value.setFromOpaqueValue(E.BaseOrMember);
-    return dyn_cast<CXXRecordDecl>(Value.getPointer());
+    return dyn_cast<CXXRecordDecl>(getAsBaseOrMember(E).getPointer());
   }
   /// Determine whether this LValue path entry for a base class names a virtual
   /// base class.
   bool isVirtualBaseClass(APValue::LValuePathEntry E) {
-    APValue::BaseOrMemberType Value;
-    Value.setFromOpaqueValue(E.BaseOrMember);
-    return Value.getInt();
+    return getAsBaseOrMember(E).getInt();
   }
 
   /// Find the path length and type of the most-derived subobject in the given
@@ -511,6 +513,22 @@ namespace {
       return CheckingPotentialConstantExpression && EvalStatus.Diag->empty();
     }
   };
+
+  /// Object used to treat all foldable expressions as constant expressions.
+  struct FoldConstant {
+    bool Enabled;
+
+    explicit FoldConstant(EvalInfo &Info)
+      : Enabled(Info.EvalStatus.Diag && Info.EvalStatus.Diag->empty() &&
+                !Info.EvalStatus.HasSideEffects) {
+    }
+    // Treat the value we've computed since this object was created as constant.
+    void Fold(EvalInfo &Info) {
+      if (Enabled && !Info.EvalStatus.Diag->empty() &&
+          !Info.EvalStatus.HasSideEffects)
+        Info.EvalStatus.Diag->clear();
+    }
+  };
 }
 
 bool SubobjectDesignator::checkSubobject(EvalInfo &Info, const Expr *E,
@@ -1480,6 +1498,59 @@ static bool ExtractSubobject(EvalInfo &Info, const Expr *E,
   return true;
 }
 
+/// Find the position where two subobject designators diverge, or equivalently
+/// the length of the common initial subsequence.
+static unsigned FindDesignatorMismatch(QualType ObjType,
+                                       const SubobjectDesignator &A,
+                                       const SubobjectDesignator &B,
+                                       bool &WasArrayIndex) {
+  unsigned I = 0, N = std::min(A.Entries.size(), B.Entries.size());
+  for (/**/; I != N; ++I) {
+    if (!ObjType.isNull() && ObjType->isArrayType()) {
+      // Next subobject is an array element.
+      if (A.Entries[I].ArrayIndex != B.Entries[I].ArrayIndex) {
+        WasArrayIndex = true;
+        return I;
+      }
+      ObjType = ObjType->castAsArrayTypeUnsafe()->getElementType();
+    } else {
+      if (A.Entries[I].BaseOrMember != B.Entries[I].BaseOrMember) {
+        WasArrayIndex = false;
+        return I;
+      }
+      if (const FieldDecl *FD = getAsField(A.Entries[I]))
+        // Next subobject is a field.
+        ObjType = FD->getType();
+      else
+        // Next subobject is a base class.
+        ObjType = QualType();
+    }
+  }
+  WasArrayIndex = false;
+  return I;
+}
+
+/// Determine whether the given subobject designators refer to elements of the
+/// same array object.
+static bool AreElementsOfSameArray(QualType ObjType,
+                                   const SubobjectDesignator &A,
+                                   const SubobjectDesignator &B) {
+  if (A.Entries.size() != B.Entries.size())
+    return false;
+
+  bool IsArray = A.MostDerivedArraySize != 0;
+  if (IsArray && A.MostDerivedPathLength != A.Entries.size())
+    // A is a subobject of the array element.
+    return false;
+
+  // If A (and B) designates an array element, the last entry will be the array
+  // index. That doesn't have to match. Otherwise, we're in the 'implicit array
+  // of length 1' case, and the entire path must match.
+  bool WasArrayIndex;
+  unsigned CommonLength = FindDesignatorMismatch(ObjType, A, B, WasArrayIndex);
+  return CommonLength >= A.Entries.size() - IsArray;
+}
+
 /// HandleLValueToRValueConversion - Perform an lvalue-to-rvalue conversion on
 /// the given lvalue. This can also be used for 'lvalue-to-lvalue' conversions
 /// for looking up the glvalue referred to by an entity of reference type.
@@ -1530,6 +1601,8 @@ static bool HandleLValueToRValueConversion(EvalInfo &Info, const Expr *Conv,
     // parameters are constant expressions even if they're non-const.
     // In C, such things can also be folded, although they are not ICEs.
     const VarDecl *VD = dyn_cast<VarDecl>(D);
+    if (const VarDecl *VDef = VD->getDefinition())
+      VD = VDef;
     if (!VD || VD->isInvalidDecl()) {
       Info.Diag(Loc);
       return false;
@@ -2279,12 +2352,35 @@ public:
   }
 
   RetTy VisitConditionalOperator(const ConditionalOperator *E) {
+    bool IsBcpCall = false;
+    // If the condition (ignoring parens) is a __builtin_constant_p call,
+    // the result is a constant expression if it can be folded without
+    // side-effects. This is an important GNU extension. See GCC PR38377
+    // for discussion.
+    if (const CallExpr *CallCE =
+          dyn_cast<CallExpr>(E->getCond()->IgnoreParenCasts()))
+      if (CallCE->isBuiltinCall() == Builtin::BI__builtin_constant_p)
+        IsBcpCall = true;
+
+    // Always assume __builtin_constant_p(...) ? ... : ... is a potential
+    // constant expression; we can't check whether it's potentially foldable.
+    if (Info.CheckingPotentialConstantExpression && IsBcpCall)
+      return false;
+
+    FoldConstant Fold(Info);
+
     bool BoolResult;
     if (!EvaluateAsBooleanCondition(E->getCond(), BoolResult, Info))
       return false;
 
     Expr *EvalExpr = BoolResult ? E->getTrueExpr() : E->getFalseExpr();
-    return StmtVisitorTy::Visit(EvalExpr);
+    if (!StmtVisitorTy::Visit(EvalExpr))
+      return false;
+
+    if (IsBcpCall)
+      Fold.Fold(Info);
+
+    return true;
   }
 
   RetTy VisitOpaqueValueExpr(const OpaqueValueExpr *E) {
@@ -4343,14 +4439,22 @@ bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
         return Success(E->getOpcode() == BO_NE, E);
       }
 
-      // FIXME: Implement the C++11 restrictions:
-      //  - Pointer subtractions must be on elements of the same array.
-      //  - Pointer comparisons must be between members with the same access.
-
       const CharUnits &LHSOffset = LHSValue.getLValueOffset();
       const CharUnits &RHSOffset = RHSValue.getLValueOffset();
 
+      SubobjectDesignator &LHSDesignator = LHSValue.getLValueDesignator();
+      SubobjectDesignator &RHSDesignator = RHSValue.getLValueDesignator();
+
       if (E->getOpcode() == BO_Sub) {
+        // C++11 [expr.add]p6:
+        //   Unless both pointers point to elements of the same array object, or
+        //   one past the last element of the array object, the behavior is
+        //   undefined.
+        if (!LHSDesignator.Invalid && !RHSDesignator.Invalid &&
+            !AreElementsOfSameArray(getType(LHSValue.Base),
+                                    LHSDesignator, RHSDesignator))
+          CCEDiag(E, diag::note_constexpr_pointer_subtraction_not_same_array);
+
         QualType Type = E->getLHS()->getType();
         QualType ElementType = Type->getAs<PointerType>()->getPointeeType();
 
@@ -4388,9 +4492,51 @@ bool IntExprEvaluator::VisitBinaryOperator(const BinaryOperator *E) {
       //   unspecified.
       // We interpret this as applying to pointers to *cv* void.
       if (LHSTy->isVoidPointerType() && LHSOffset != RHSOffset &&
-          E->getOpcode() != BO_EQ && E->getOpcode() != BO_NE)
+          E->isRelationalOp())
         CCEDiag(E, diag::note_constexpr_void_comparison);
 
+      // C++11 [expr.rel]p2:
+      // - If two pointers point to non-static data members of the same object,
+      //   or to subobjects or array elements fo such members, recursively, the
+      //   pointer to the later declared member compares greater provided the
+      //   two members have the same access control and provided their class is
+      //   not a union.
+      //   [...]
+      // - Otherwise pointer comparisons are unspecified.
+      if (!LHSDesignator.Invalid && !RHSDesignator.Invalid &&
+          E->isRelationalOp()) {
+        bool WasArrayIndex;
+        unsigned Mismatch =
+          FindDesignatorMismatch(getType(LHSValue.Base), LHSDesignator,
+                                 RHSDesignator, WasArrayIndex);
+        // At the point where the designators diverge, the comparison has a
+        // specified value if:
+        //  - we are comparing array indices
+        //  - we are comparing fields of a union, or fields with the same access
+        // Otherwise, the result is unspecified and thus the comparison is not a
+        // constant expression.
+        if (!WasArrayIndex && Mismatch < LHSDesignator.Entries.size() &&
+            Mismatch < RHSDesignator.Entries.size()) {
+          const FieldDecl *LF = getAsField(LHSDesignator.Entries[Mismatch]);
+          const FieldDecl *RF = getAsField(RHSDesignator.Entries[Mismatch]);
+          if (!LF && !RF)
+            CCEDiag(E, diag::note_constexpr_pointer_comparison_base_classes);
+          else if (!LF)
+            CCEDiag(E, diag::note_constexpr_pointer_comparison_base_field)
+              << getAsBaseClass(LHSDesignator.Entries[Mismatch])
+              << RF->getParent() << RF;
+          else if (!RF)
+            CCEDiag(E, diag::note_constexpr_pointer_comparison_base_field)
+              << getAsBaseClass(RHSDesignator.Entries[Mismatch])
+              << LF->getParent() << LF;
+          else if (!LF->getParent()->isUnion() &&
+                   LF->getAccess() != RF->getAccess())
+            CCEDiag(E, diag::note_constexpr_pointer_comparison_differing_access)
+              << LF << LF->getAccess() << RF << RF->getAccess()
+              << LF->getParent();
+        }
+      }
+
       switch (E->getOpcode()) {
       default: llvm_unreachable("missing comparison operator");
       case BO_LT: return Success(LHSOffset < RHSOffset, E);
diff --git a/test/CXX/dcl.dcl/dcl.spec/dcl.constexpr/p5.cpp b/test/CXX/dcl.dcl/dcl.spec/dcl.constexpr/p5.cpp
index e65e0e27aa..43fc887b00 100644
--- a/test/CXX/dcl.dcl/dcl.spec/dcl.constexpr/p5.cpp
+++ b/test/CXX/dcl.dcl/dcl.spec/dcl.constexpr/p5.cpp
@@ -72,4 +72,10 @@ constexpr S InitList3(int a) { return a ? (S){ a, a } : (S){ a, ng }; }; // ok
 // expression with an unknown value, and diagnose if neither is constant.
 constexpr S InitList4(int a) { return a ? (S){ a, ng } : (S){ a, ng }; };
 
+// __builtin_constant_p ? : is magical, and is always a potential constant.
+constexpr bool BcpCall(int n) {
+  return __builtin_constant_p((int*)n != &n) ? (int*)n != &n : (int*)n != &n;
+}
+static_assert(BcpCall(0), "");
+
 }
diff --git a/test/CXX/expr/expr.const/p2-0x.cpp b/test/CXX/expr/expr.const/p2-0x.cpp
index 8e68b9a0fb..0b22151a87 100644
--- a/test/CXX/expr/expr.const/p2-0x.cpp
+++ b/test/CXX/expr/expr.const/p2-0x.cpp
@@ -109,7 +109,6 @@ namespace RecursionLimits {
   };
 }
 
-// FIXME:
 // - an operation that would have undefined behavior [Note: including, for
 //   example, signed integer overflow (Clause 5 [expr]), certain pointer
 //   arithmetic (5.7 [expr.add]), division by zero (5.6 [expr.mul]), or certain
@@ -195,6 +194,15 @@ namespace UndefinedBehavior {
     constexpr int k3 = (&c)[1].f(); // expected-error {{constant expression}} expected-note {{cannot call member function on pointer past the end of object}}
     C c2;
     constexpr int k4 = c2.f(); // ok!
+
+    constexpr int diff1 = &a[2] - &a[0];
+    constexpr int diff2 = &a[1][3] - &a[1][0];
+    constexpr int diff3 = &a[2][0] - &a[1][0]; // expected-error {{constant expression}} expected-note {{subtracted pointers are not elements of the same array}}
+    static_assert(&a[2][0] == &a[1][3], "");
+    constexpr int diff4 = (&b + 1) - &b;
+    constexpr int diff5 = &a[1][2].n - &a[1][0].n; // expected-error {{constant expression}} expected-note {{subtracted pointers are not elements of the same array}}
+    constexpr int diff6 = &a[1][2].n - &a[1][2].n;
+    constexpr int diff7 = (A*)&a[0][1] - (A*)&a[0][0]; // expected-error {{constant expression}} expected-note {{subtracted pointers are not elements of the same array}}
   }
 
   namespace Overflow {
@@ -293,8 +301,6 @@ namespace LValueToRValue {
   static_assert(((volatile const S&&)(S)0).i, ""); // expected-error {{constant expression}} expected-note {{subexpression}}
 }
 
-// FIXME:
-//
 // DR1312: The proposed wording for this defect has issues, so we ignore this
 // bullet and instead prohibit casts from pointers to cv void (see core-20842
 // and core-20845).
@@ -303,9 +309,23 @@ namespace LValueToRValue {
 // glvalue of type cv1 T that refers to an object of type cv2 U, where T and U
 // are neither the same type nor similar types (4.4 [conv.qual]);
 
-// FIXME:
 // - an lvalue-to-rvalue conversion (4.1) that is applied to a glvalue that
 // refers to a non-active member of a union or a subobject thereof;
+namespace LValueToRValueUnion {
+  // test/SemaCXX/constant-expression-cxx11.cpp contains more thorough testing
+  // of this.
+  union U { int a, b; } constexpr u = U();
+  static_assert(u.a == 0, "");
+  constexpr const int *bp = &u.b;
+  constexpr int b = *bp; // expected-error {{constant expression}} expected-note {{read of member 'b' of union with active member 'a'}}
+
+  extern const U pu;
+  constexpr const int *pua = &pu.a;
+  constexpr const int *pub = &pu.b;
+  constexpr U pu = { .b = 1 }; // expected-warning {{C99 feature}}
+  constexpr const int a2 = *pua; // expected-error {{constant expression}} expected-note {{read of member 'a' of union with active member 'b'}}
+  constexpr const int b2 = *pub; // ok
+}
 
 // - an id-expression that refers to a variable or data member of reference type
 //   unless the reference has a preceding initialization, initialized with a
@@ -431,9 +451,43 @@ namespace UnspecifiedRelations {
   constexpr bool u13 = pf < pg; // expected-error {{constant expression}}
   constexpr bool u14 = pf == pg;
 
-  // FIXME:
   // If two pointers point to non-static data members of the same object with
   // different access control, the result is unspecified.
+  struct A {
+  public:
+    constexpr A() : a(0), b(0) {}
+    int a;
+    constexpr bool cmp() { return &a < &b; } // expected-error {{constexpr function never produces a constant expression}} expected-note {{comparison of address of fields 'a' and 'b' of 'A' with differing access specifiers (public vs private) has unspecified value}}
+  private:
+    int b;
+  };
+  class B {
+  public:
+    A a;
+    constexpr bool cmp() { return &a.a < &b.a; } // expected-error {{constexpr function never produces a constant expression}} expected-note {{comparison of address of fields 'a' and 'b' of 'B' with differing access specifiers (public vs protected) has unspecified value}}
+  protected:
+    A b;
+  };
+
+  // If two pointers point to different base sub-objects of the same object, or
+  // one points to a base subobject and the other points to a member, the result
+  // of the comparison is unspecified. This is not explicitly called out by
+  // [expr.rel]p2, but is covered by 'Other pointer comparisons are
+  // unspecified'.
+  struct C {
+    int c[2];
+  };
+  struct D {
+    int d;
+  };
+  struct E : C, D {
+    struct Inner {
+      int f;
+    } e;
+  } e;
+  constexpr bool base1 = &e.c[0] < &e.d; // expected-error {{constant expression}} expected-note {{comparison of addresses of subobjects of different base classes has unspecified value}}
+  constexpr bool base2 = &e.c[1] < &e.e.f; // expected-error {{constant expression}} expected-note {{comparison of address of base class subobject 'C' of class 'E' to field 'e' has unspecified value}}
+  constexpr bool base3 = &e.e.f < &e.d; // expected-error {{constant expression}} expected-note {{comparison of address of base class subobject 'D' of class 'E' to field 'e' has unspecified value}}
 
   // [expr.rel]p3: Pointers to void can be compared [...] if both pointers
   // represent the same address or are both the null pointer [...]; otherwise
@@ -450,10 +504,6 @@ namespace UnspecifiedRelations {
   constexpr bool v6 = qv > null; // expected-error {{constant expression}}
   constexpr bool v7 = qv <= (void*)&s.b; // ok
   constexpr bool v8 = qv > (void*)&s.a; // expected-error {{constant expression}} expected-note {{unequal pointers to void}}
-
-  // FIXME: Implement comparisons of pointers to members.
-  // [expr.eq]p2: If either is a pointer to a virtual member function and
-  // neither is null, the result is unspecified.
 }
 
 // - an assignment or a compound assignment (5.17); or
diff --git a/test/SemaCXX/constant-expression-cxx11.cpp b/test/SemaCXX/constant-expression-cxx11.cpp
index 5a05cf3c78..36736ad297 100644
--- a/test/SemaCXX/constant-expression-cxx11.cpp
+++ b/test/SemaCXX/constant-expression-cxx11.cpp
@@ -37,6 +37,7 @@ namespace DerivedToVBaseCast {
   D d;
   constexpr B *p = &d;
   constexpr C *q = &d;
+
   static_assert((void*)p != (void*)q, "");
   static_assert((A*)p == (A*)q, "");
   static_assert((Aa*)p != (Aa*)q, "");
@@ -65,7 +66,6 @@ namespace DerivedToVBaseCast {
   struct Z : Y1, Y2 {};
   Z z;
   static_assert((X*)(Y1*)&z != (X*)(Y2*)&z, "");
-
 }
 
 namespace ConstCast {
@@ -666,7 +666,7 @@ static_assert(&bot1 != &bot2, "");
 
 constexpr Bottom *pb1 = (Base*)&derived;
 constexpr Bottom *pb2 = (Base2*)&derived;
-static_assert(pb1 != pb2, "");
+static_assert(&pb1 != &pb2, "");
 static_assert(pb1 == &bot1, "");
 static_assert(pb2 == &bot2, "");
 
@@ -1113,3 +1113,17 @@ namespace IndirectField {
   static_assert(s2.e == 0, ""); // expected-error {{constant expression}} expected-note {{union with active member}}
   static_assert(s2.f == 7, "");
 }
+
+namespace Fold {
+
+  // This macro forces its argument to be constant-folded, even if it's not
+  // otherwise a constant expression.
+  #define fold(x) (__builtin_constant_p(x) ? (x) : (x))
+
+  constexpr int n = (int)(char*)123; // expected-error {{constant expression}} expected-note {{reinterpret_cast}}
+  constexpr int m = fold((int)(char*)123); // ok
+  static_assert(m == 123, "");
+
+  #undef fold
+
+}