From cc5d4f637cdf83adc174b96d2bfe27cef1cf0f36 Mon Sep 17 00:00:00 2001 From: Richard Smith Date: Mon, 7 Nov 2011 09:22:26 +0000 Subject: [PATCH] Constant expression evaluation: support for arrays. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@143922 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/APValue.h | 76 +++++++--- lib/AST/APValue.cpp | 45 +++++- lib/AST/ExprConstant.cpp | 160 ++++++++++++++++----- lib/CodeGen/CGExprConstant.cpp | 3 + test/SemaCXX/constant-expression-cxx11.cpp | 42 ++++++ 5 files changed, 273 insertions(+), 53 deletions(-) diff --git a/include/clang/AST/APValue.h b/include/clang/AST/APValue.h index 664a78f5d0..57c89d62be 100644 --- a/include/clang/AST/APValue.h +++ b/include/clang/AST/APValue.h @@ -25,7 +25,8 @@ namespace clang { class Decl; /// APValue - This class implements a discriminated union of [uninitialized] -/// [APSInt] [APFloat], [Complex APSInt] [Complex APFloat], [Expr + Offset]. +/// [APSInt] [APFloat], [Complex APSInt] [Complex APFloat], [Expr + Offset], +/// [Vector: N * APValue], [Array: N * APValue] class APValue { typedef llvm::APSInt APSInt; typedef llvm::APFloat APFloat; @@ -37,13 +38,15 @@ public: ComplexInt, ComplexFloat, LValue, - Vector + Vector, + Array }; union LValuePathEntry { const Decl *BaseOrMember; uint64_t ArrayIndex; }; struct NoLValuePath {}; + struct UninitArray {}; private: ValueKind Kind; @@ -55,15 +58,19 @@ private: APFloat Real, Imag; ComplexAPFloat() : Real(0.0), Imag(0.0) {} }; - + struct LV; struct Vec { APValue *Elts; unsigned NumElts; Vec() : Elts(0), NumElts(0) {} ~Vec() { delete[] Elts; } }; - - struct LV; + struct Arr { + APValue *Elts; + unsigned NumElts, ArrSize; + Arr(unsigned NumElts, unsigned ArrSize); + ~Arr(); + }; enum { MaxSize = (sizeof(ComplexAPSInt) > sizeof(ComplexAPFloat) ? @@ -104,6 +111,9 @@ public: MakeLValue(); setLValue(B, O, Path); } APValue(const Expr *B); + APValue(UninitArray, unsigned InitElts, unsigned Size) : Kind(Uninitialized) { + MakeArray(InitElts, Size); + } ~APValue() { MakeUninit(); @@ -117,6 +127,7 @@ public: bool isComplexFloat() const { return Kind == ComplexFloat; } bool isLValue() const { return Kind == LValue; } bool isVector() const { return Kind == Vector; } + bool isArray() const { return Kind == Array; } void print(raw_ostream &OS) const; void dump() const; @@ -137,19 +148,6 @@ public: return const_cast(this)->getFloat(); } - APValue &getVectorElt(unsigned i) { - assert(isVector() && "Invalid accessor"); - return ((Vec*)(char*)Data)->Elts[i]; - } - const APValue &getVectorElt(unsigned i) const { - assert(isVector() && "Invalid accessor"); - return ((const Vec*)(const char*)Data)->Elts[i]; - } - unsigned getVectorLength() const { - assert(isVector() && "Invalid accessor"); - return ((const Vec*)(const void *)Data)->NumElts; - } - APSInt &getComplexIntReal() { assert(isComplexInt() && "Invalid accessor"); return ((ComplexAPSInt*)(char*)Data)->Real; @@ -190,6 +188,47 @@ public: bool hasLValuePath() const; ArrayRef getLValuePath() const; + APValue &getVectorElt(unsigned I) { + assert(isVector() && "Invalid accessor"); + assert(I < getVectorLength() && "Index out of range"); + return ((Vec*)(char*)Data)->Elts[I]; + } + const APValue &getVectorElt(unsigned I) const { + return const_cast(this)->getVectorElt(I); + } + unsigned getVectorLength() const { + assert(isVector() && "Invalid accessor"); + return ((const Vec*)(const void *)Data)->NumElts; + } + + APValue &getArrayInitializedElt(unsigned I) { + assert(isArray() && "Invalid accessor"); + assert(I < getArrayInitializedElts() && "Index out of range"); + return ((Arr*)(char*)Data)->Elts[I]; + } + const APValue &getArrayInitializedElt(unsigned I) const { + return const_cast(this)->getArrayInitializedElt(I); + } + bool hasArrayFiller() const { + return getArrayInitializedElts() != getArraySize(); + } + APValue &getArrayFiller() { + assert(isArray() && "Invalid accessor"); + assert(hasArrayFiller() && "No array filler"); + return ((Arr*)(char*)Data)->Elts[getArrayInitializedElts()]; + } + const APValue &getArrayFiller() const { + return const_cast(this)->getArrayFiller(); + } + unsigned getArrayInitializedElts() const { + assert(isArray() && "Invalid accessor"); + return ((const Arr*)(const void *)Data)->NumElts; + } + unsigned getArraySize() const { + assert(isArray() && "Invalid accessor"); + return ((const Arr*)(const void *)Data)->ArrSize; + } + void setInt(const APSInt &I) { assert(isInt() && "Invalid accessor"); *(APSInt*)(char*)Data = I; @@ -253,6 +292,7 @@ private: Kind = ComplexFloat; } void MakeLValue(); + void MakeArray(unsigned InitElts, unsigned Size); }; inline raw_ostream &operator<<(raw_ostream &OS, const APValue &V) { diff --git a/lib/AST/APValue.cpp b/lib/AST/APValue.cpp index e2f7c61937..af34642bea 100644 --- a/lib/AST/APValue.cpp +++ b/lib/AST/APValue.cpp @@ -55,6 +55,13 @@ struct APValue::LV : LVBase { } }; +// FIXME: Reduce the malloc traffic here. + +APValue::Arr::Arr(unsigned NumElts, unsigned Size) : + Elts(new APValue[NumElts + (NumElts != Size ? 1 : 0)]), + NumElts(NumElts), ArrSize(Size) {} +APValue::Arr::~Arr() { delete [] Elts; } + APValue::APValue(const Expr* B) : Kind(Uninitialized) { MakeLValue(); setLValue(B, CharUnits::Zero(), ArrayRef()); @@ -75,6 +82,8 @@ const APValue &APValue::operator=(const APValue &RHS) { MakeComplexFloat(); else if (RHS.isLValue()) MakeLValue(); + else if (RHS.isArray()) + MakeArray(RHS.getArrayInitializedElts(), RHS.getArraySize()); } if (isInt()) setInt(RHS.getInt()); @@ -92,6 +101,11 @@ const APValue &APValue::operator=(const APValue &RHS) { setLValue(RHS.getLValueBase(), RHS.getLValueOffset(),RHS.getLValuePath()); else setLValue(RHS.getLValueBase(), RHS.getLValueOffset(), NoLValuePath()); + } else if (isArray()) { + for (unsigned I = 0, N = RHS.getArrayInitializedElts(); I != N; ++I) + getArrayInitializedElt(I) = RHS.getArrayInitializedElt(I); + if (RHS.hasArrayFiller()) + getArrayFiller() = RHS.getArrayFiller(); } return *this; } @@ -107,9 +121,10 @@ void APValue::MakeUninit() { ((ComplexAPSInt*)(char*)Data)->~ComplexAPSInt(); else if (Kind == ComplexFloat) ((ComplexAPFloat*)(char*)Data)->~ComplexAPFloat(); - else if (Kind == LValue) { + else if (Kind == LValue) ((LV*)(char*)Data)->~LV(); - } + else if (Kind == Array) + ((Arr*)(char*)Data)->~Arr(); Kind = Uninitialized; } @@ -149,9 +164,20 @@ void APValue::print(raw_ostream &OS) const { case ComplexFloat: OS << "ComplexFloat: " << GetApproxValue(getComplexFloatReal()) << ", " << GetApproxValue(getComplexFloatImag()); + return; case LValue: OS << "LValue: "; return; + case Array: + OS << "Array: "; + for (unsigned I = 0, N = getArrayInitializedElts(); I != N; ++I) { + OS << getArrayInitializedElt(I); + if (I != getArraySize() - 1) OS << ", "; + } + if (hasArrayFiller()) + OS << getArraySize() - getArrayInitializedElts() << " x " + << getArrayFiller(); + return; } } @@ -187,6 +213,15 @@ static void WriteShortAPValueToStream(raw_ostream& Out, case APValue::LValue: Out << "LValue: "; break; + case APValue::Array: + Out << '{'; + if (unsigned N = V.getArrayInitializedElts()) { + Out << V.getArrayInitializedElt(0); + for (unsigned I = 1; I != N; ++I) + Out << ", " << V.getArrayInitializedElt(I); + } + Out << '}'; + break; } } @@ -244,3 +279,9 @@ void APValue::MakeLValue() { new ((void*)(char*)Data) LV(); Kind = LValue; } + +void APValue::MakeArray(unsigned InitElts, unsigned Size) { + assert(isUninit() && "Bad state change"); + new ((void*)(char*)Data) Arr(InitElts, Size); + Kind = Array; +} diff --git a/lib/AST/ExprConstant.cpp b/lib/AST/ExprConstant.cpp index a9408f6384..746b094619 100644 --- a/lib/AST/ExprConstant.cpp +++ b/lib/AST/ExprConstant.cpp @@ -132,6 +132,7 @@ namespace { void adjustIndex(uint64_t N) { if (Invalid) return; if (ArrayElement) { + // FIXME: Make sure the index stays within bounds, or one past the end. Entries.back().ArrayIndex += N; return; } @@ -475,6 +476,7 @@ static bool HandleConversionToBool(const CCValue &Val, bool &Result) { return EvalPointerValueAsBool(PointerResult, Result); } case APValue::Vector: + case APValue::Array: return false; } @@ -569,6 +571,13 @@ static bool EvaluateVarDeclInit(EvalInfo &Info, const VarDecl *VD, // expression. If not, we should propagate up a diagnostic. APValue EvalResult; if (!EvaluateConstantExpression(EvalResult, InitInfo, Init)) { + // FIXME: If the evaluation failure was not permanent (for instance, if we + // hit a variable with no declaration yet, or a constexpr function with no + // definition yet), the standard is unclear as to how we should behave. + // + // Either the initializer should be evaluated when the variable is defined, + // or a failed evaluation of the initializer should be reattempted each time + // it is used. VD->setEvaluatedValue(APValue()); return false; } @@ -583,8 +592,48 @@ static bool IsConstNonVolatile(QualType T) { return Quals.hasConst() && !Quals.hasVolatile(); } -bool HandleLValueToRValueConversion(EvalInfo &Info, QualType Type, - const LValue &LVal, CCValue &RVal) { +/// Extract the designated sub-object of an rvalue. +static bool ExtractSubobject(EvalInfo &Info, CCValue &Obj, QualType ObjType, + const SubobjectDesignator &Sub, QualType SubType) { + if (Sub.Invalid || Sub.OnePastTheEnd) + return false; + if (Sub.Entries.empty()) { + assert(Info.Ctx.hasSameUnqualifiedType(ObjType, SubType) && + "Unexpected subobject type"); + return true; + } + + assert(!Obj.isLValue() && "extracting subobject of lvalue"); + const APValue *O = &Obj; + for (unsigned I = 0, N = Sub.Entries.size(); I != N; ++I) { + if (O->isUninit()) + return false; + if (ObjType->isArrayType()) { + const ConstantArrayType *CAT = Info.Ctx.getAsConstantArrayType(ObjType); + if (!CAT) + return false; + uint64_t Index = Sub.Entries[I].ArrayIndex; + if (CAT->getSize().ule(Index)) + return false; + if (O->getArrayInitializedElts() > Index) + O = &O->getArrayInitializedElt(Index); + else + O = &O->getArrayFiller(); + ObjType = CAT->getElementType(); + } else { + // FIXME: Support handling of subobjects of structs and unions. Also + // for vector elements, if we want to support those? + } + } + + assert(Info.Ctx.hasSameUnqualifiedType(ObjType, SubType) && + "Unexpected subobject type"); + Obj = CCValue(*O, CCValue::GlobalValue()); + return true; +} + +static bool HandleLValueToRValueConversion(EvalInfo &Info, QualType Type, + const LValue &LVal, CCValue &RVal) { const Expr *Base = LVal.Base; CallStackFrame *Frame = LVal.Frame; @@ -620,10 +669,7 @@ bool HandleLValueToRValueConversion(EvalInfo &Info, QualType Type, return false; if (isa(VD) || !VD->getAnyInitializer()->isLValue()) - // If the lvalue refers to a subobject or has been cast to some other - // type, don't use it. - return LVal.Offset.isZero() && - Info.Ctx.hasSameUnqualifiedType(Type, VT); + return ExtractSubobject(Info, RVal, VT, LVal.Designator, Type); // The declaration was initialized by an lvalue, with no lvalue-to-rvalue // conversion. This happens when the declaration and the lvalue should be @@ -654,31 +700,22 @@ bool HandleLValueToRValueConversion(EvalInfo &Info, QualType Type, return true; } - // FIXME: Support accessing subobjects of objects of literal types. A simple - // byte offset is insufficient for C++11 semantics: we need to know how the - // reference was formed (which union member was named, for instance). - - // Beyond this point, we don't support accessing subobjects. - if (!LVal.Offset.isZero() || - !Info.Ctx.hasSameUnqualifiedType(Type, Base->getType())) - return false; - - // If this is a temporary expression with a nontrivial initializer, grab the - // value from the relevant stack frame. if (Frame) { + // If this is a temporary expression with a nontrivial initializer, grab the + // value from the relevant stack frame. RVal = Frame->Temporaries[Base]; - return true; - } - - // In C99, a CompoundLiteralExpr is an lvalue, and we defer evaluating the - // initializer until now for such expressions. Such an expression can't be - // an ICE in C, so this only matters for fold. - if (const CompoundLiteralExpr *CLE = dyn_cast(Base)) { + } else if (const CompoundLiteralExpr *CLE + = dyn_cast(Base)) { + // In C99, a CompoundLiteralExpr is an lvalue, and we defer evaluating the + // initializer until now for such expressions. Such an expression can't be + // an ICE in C, so this only matters for fold. assert(!Info.getLangOpts().CPlusPlus && "lvalue compound literal in c++?"); - return Evaluate(RVal, Info, CLE->getInitializer()); - } + if (!Evaluate(RVal, Info, CLE->getInitializer())) + return false; + } else + return false; - return false; + return ExtractSubobject(Info, RVal, Base->getType(), LVal.Designator, Type); } namespace { @@ -1599,6 +1636,55 @@ bool VectorExprEvaluator::VisitUnaryImag(const UnaryOperator *E) { return ValueInitialization(E); } +//===----------------------------------------------------------------------===// +// Array Evaluation +//===----------------------------------------------------------------------===// + +namespace { + class ArrayExprEvaluator + : public ExprEvaluatorBase { + APValue &Result; + public: + + ArrayExprEvaluator(EvalInfo &Info, APValue &Result) + : ExprEvaluatorBaseTy(Info), Result(Result) {} + + bool Success(const APValue &V, const Expr *E) { + assert(V.isArray() && "Expected array type"); + Result = V; + return true; + } + bool Error(const Expr *E) { return false; } + + bool VisitInitListExpr(const InitListExpr *E); + }; +} // end anonymous namespace + +static bool EvaluateArray(const Expr* E, APValue& Result, EvalInfo &Info) { + assert(E->isRValue() && E->getType()->isArrayType() && + E->getType()->isLiteralType() && "not a literal array rvalue"); + return ArrayExprEvaluator(Info, Result).Visit(E); +} + +bool ArrayExprEvaluator::VisitInitListExpr(const InitListExpr *E) { + const ConstantArrayType *CAT = Info.Ctx.getAsConstantArrayType(E->getType()); + if (!CAT) + return false; + + Result = APValue(APValue::UninitArray(), E->getNumInits(), + CAT->getSize().getZExtValue()); + for (InitListExpr::const_iterator I = E->begin(), End = E->end(); + I != End; ++I) + if (!EvaluateConstantExpression(Result.getArrayInitializedElt(I-E->begin()), + Info, cast(*I))) + return false; + + if (!Result.hasArrayFiller()) return true; + assert(E->hasArrayFiller() && "no array filler for incomplete init list"); + return EvaluateConstantExpression(Result.getArrayFiller(), Info, + E->getArrayFiller()); +} + //===----------------------------------------------------------------------===// // Integer Evaluation // @@ -2173,6 +2259,10 @@ 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. + if (E->getOpcode() == BO_Sub) { QualType Type = E->getLHS()->getType(); QualType ElementType = Type->getAs()->getPointeeType(); @@ -3258,8 +3348,8 @@ static bool Evaluate(CCValue &Result, EvalInfo &Info, const Expr *E) { // FIXME: Implement evaluation of pointer-to-member types. return false; } else if (E->getType()->isArrayType() && E->getType()->isLiteralType()) { - // FIXME: Implement evaluation of array rvalues. - return false; + if (!EvaluateArray(E, Result, Info)) + return false; } else if (E->getType()->isRecordType() && E->getType()->isLiteralType()) { // FIXME: Implement evaluation of record rvalues. return false; @@ -3278,10 +3368,10 @@ static bool EvaluateConstantExpression(APValue &Result, EvalInfo &Info, if (E->isRValue() && E->getType()->isLiteralType()) { // Evaluate arrays and record types in-place, so that later initializers can // refer to earlier-initialized members of the object. - if (E->getType()->isArrayType()) - // FIXME: Implement evaluation of array rvalues. - return false; - else if (E->getType()->isRecordType()) + if (E->getType()->isArrayType()) { + if (!EvaluateArray(E, Result, Info)) + return false; + } else if (E->getType()->isRecordType()) // FIXME: Implement evaluation of record rvalues. return false; } @@ -3312,6 +3402,10 @@ bool Expr::EvaluateAsRValue(EvalResult &Result, const ASTContext &Ctx) const { return false; } + // Don't produce array constants until CodeGen is taught to handle them. + if (Value.isArray()) + return false; + // Check this core constant expression is a constant expression, and if so, // convert it to one. return CheckConstantExpression(Value, Result.Val); diff --git a/lib/CodeGen/CGExprConstant.cpp b/lib/CodeGen/CGExprConstant.cpp index 7a1cbdeb1e..897ea02e58 100644 --- a/lib/CodeGen/CGExprConstant.cpp +++ b/lib/CodeGen/CGExprConstant.cpp @@ -1070,6 +1070,9 @@ llvm::Constant *CodeGenModule::EmitConstantExpr(const Expr *E, } return llvm::ConstantVector::get(Inits); } + case APValue::Array: + assert(0 && "shouldn't see array constants here yet"); + break; } } diff --git a/test/SemaCXX/constant-expression-cxx11.cpp b/test/SemaCXX/constant-expression-cxx11.cpp index 010914e6f4..bba949bbd5 100644 --- a/test/SemaCXX/constant-expression-cxx11.cpp +++ b/test/SemaCXX/constant-expression-cxx11.cpp @@ -280,3 +280,45 @@ static_assert_fold(*max == 'z', ""); static_assert_fold(max == str + 38, ""); } + +namespace Array { + +// FIXME: Use templates for these once we support constexpr templates. +constexpr int Sum(const int *begin, const int *end) { + return begin == end ? 0 : *begin + Sum(begin+1, end); +} +constexpr const int *begin(const int (&xs)[5]) { return xs; } +constexpr const int *end(const int (&xs)[5]) { return xs + 5; } + +constexpr int xs[] = { 1, 2, 3, 4, 5 }; +constexpr int ys[] = { 5, 4, 3, 2, 1 }; +constexpr int sum_xs = Sum(begin(xs), end(xs)); +static_assert_fold(sum_xs == 15, ""); + +constexpr int ZipFoldR(int (*F)(int x, int y, int c), int n, + const int *xs, const int *ys, int c) { + return n ? F(*xs, *ys, ZipFoldR(F, n-1, xs+1, ys+1, c)) : c; +} +constexpr int MulAdd(int x, int y, int c) { return x * y + c; } +constexpr int InnerProduct = ZipFoldR(MulAdd, 5, xs, ys, 0); +static_assert_fold(InnerProduct == 35, ""); + +constexpr int SubMul(int x, int y, int c) { return (x - y) * c; } +constexpr int DiffProd = ZipFoldR(SubMul, 2, xs+3, ys+3, 1); +static_assert_fold(DiffProd == 8, ""); +static_assert_fold(ZipFoldR(SubMul, 3, xs+3, ys+3, 1), ""); // expected-error {{constant expression}} + +constexpr const int *p = xs + 3; +constexpr int xs4 = p[1]; // ok +constexpr int xs5 = p[2]; // expected-error {{constant expression}} +constexpr int xs0 = p[-3]; // ok +constexpr int xs_1 = p[-4]; // expected-error {{constant expression}} + +constexpr int zs[2][2][2][2] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 }; +static_assert_fold(zs[0][0][0][0] == 1, ""); +static_assert_fold(zs[1][1][1][1] == 16, ""); +static_assert_fold(zs[0][0][0][2] == 3, ""); // expected-error {{constant expression}} +static_assert_fold((&zs[0][0][0][2])[-1] == 2, ""); +static_assert_fold(**(**(zs + 1) + 1) == 11, ""); + +} -- 2.40.0