From 78d1583d0b36b7d6d8d10234cdc19ab94adf765a Mon Sep 17 00:00:00 2001 From: Douglas Gregor Date: Tue, 26 May 2009 18:54:04 +0000 Subject: [PATCH] When evaluating a VarDecl as a constant or determining whether it is an integral constant expression, maintain a cache of the value and the is-an-ICE flag within the VarDecl itself. This eliminates exponential-time behavior of the Fibonacci template metaprogram. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@72428 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/clang/AST/Decl.h | 119 +++++++++++++++++++++++++++++++-- lib/AST/Decl.cpp | 16 ++++- lib/AST/Expr.cpp | 17 ++++- lib/AST/ExprConstant.cpp | 13 +++- lib/AST/StmtIterator.cpp | 4 +- lib/Frontend/PCHReaderDecl.cpp | 2 +- lib/Sema/SemaDecl.cpp | 4 +- lib/Sema/SemaDeclCXX.cpp | 2 +- 8 files changed, 160 insertions(+), 17 deletions(-) diff --git a/include/clang/AST/Decl.h b/include/clang/AST/Decl.h index 4c4763f48e..a30cf0fbc5 100644 --- a/include/clang/AST/Decl.h +++ b/include/clang/AST/Decl.h @@ -14,6 +14,7 @@ #ifndef LLVM_CLANG_AST_DECL_H #define LLVM_CLANG_AST_DECL_H +#include "clang/AST/APValue.h" #include "clang/AST/DeclBase.h" #include "clang/AST/DeclarationName.h" #include "clang/AST/ExternalASTSource.h" @@ -186,6 +187,27 @@ public: static bool classof(const ValueDecl *D) { return true; } }; +/// \brief Structure used to store a statement, the constant value to +/// which it was evaluated (if any), and whether or not the statement +/// is an integral constant expression (if known). +struct EvaluatedStmt { + EvaluatedStmt() : WasEvaluated(false), CheckedICE(false), IsICE(false) { } + + /// \brief Whether this statement was already evaluated. + bool WasEvaluated : 1; + + /// \brief Whether we already checked whether this statement was an + /// integral constant expression. + bool CheckedICE : 1; + + /// \brief Whether this statement is an integral constant + /// expression. Only valid if CheckedICE is true. + bool IsICE : 1; + + Stmt *Value; + APValue Evaluated; +}; + /// VarDecl - An instance of this class is created to represent a variable /// declaration or definition. class VarDecl : public ValueDecl { @@ -201,7 +223,7 @@ public: static const char *getStorageClassSpecifierString(StorageClass SC); private: - Stmt *Init; + mutable llvm::PointerUnion Init; // FIXME: This can be packed into the bitfields in Decl. unsigned SClass : 3; bool ThreadSpecified : 1; @@ -220,7 +242,7 @@ private: protected: VarDecl(Kind DK, DeclContext *DC, SourceLocation L, IdentifierInfo *Id, QualType T, StorageClass SC, SourceLocation TSSL = SourceLocation()) - : ValueDecl(DK, DC, L, Id, T), Init(0), + : ValueDecl(DK, DC, L, Id, T), Init(), ThreadSpecified(false), HasCXXDirectInit(false), DeclaredInCondition(false), PreviousDeclaration(0), TypeSpecStartLoc(TSSL) { @@ -243,10 +265,95 @@ public: TypeSpecStartLoc = SL; } - const Expr *getInit() const { return (const Expr*) Init; } - Expr *getInit() { return (Expr*) Init; } - void setInit(Expr *I) { Init = (Stmt*) I; } - + const Expr *getInit() const { + if (Init.isNull()) + return 0; + + const Stmt *S = Init.dyn_cast(); + if (!S) + S = Init.get()->Value; + + return (const Expr*) S; + } + Expr *getInit() { + if (Init.isNull()) + return 0; + + Stmt *S = Init.dyn_cast(); + if (!S) + S = Init.get()->Value; + + return (Expr*) S; + } + + /// \brief Retrieve the address of the initializer expression. + Stmt **getInitAddress() { + if (Init.is()) + return reinterpret_cast(&Init); // FIXME: ugly hack + return &Init.get()->Value; + } + + void setInit(ASTContext &C, Expr *I); + + /// \brief Note that constant evaluation has computed the given + /// value for this variable's initializer. + void setEvaluatedValue(ASTContext &C, const APValue &Value) const { + EvaluatedStmt *Eval = Init.dyn_cast(); + if (!Eval) { + Stmt *S = Init.get(); + Eval = new (C) EvaluatedStmt; + Eval->Value = S; + Init = Eval; + } + + Eval->WasEvaluated = true; + Eval->Evaluated = Value; + } + + /// \brief Return the already-evaluated value of this variable's + /// initializer, or NULL if the value is not yet known. + APValue *getEvaluatedValue() const { + if (EvaluatedStmt *Eval = Init.dyn_cast()) + if (Eval->WasEvaluated) + return &Eval->Evaluated; + + return 0; + } + + /// \brief Determines whether it is already known whether the + /// initializer is an integral constant expression or not. + bool isInitKnownICE() const { + if (EvaluatedStmt *Eval = Init.dyn_cast()) + return Eval->CheckedICE; + + return false; + } + + /// \brief Determines whether the initializer is an integral + /// constant expression. + /// + /// \pre isInitKnownICE() + bool isInitICE() const { + assert(isInitKnownICE() && + "Check whether we already know that the initializer is an ICE"); + return Init.get()->IsICE; + } + + /// \brief Note that we now know whether the initializer is an + /// integral constant expression. + void setInitKnownICE(ASTContext &C, bool IsICE) const { + EvaluatedStmt *Eval = Init.dyn_cast(); + if (!Eval) { + Stmt *S = Init.get(); + Eval = new (C) EvaluatedStmt; + Eval->Value = S; + Init = Eval; + } + + Eval->CheckedICE = true; + Eval->IsICE = IsICE; + } + /// \brief Retrieve the definition of this variable, which may come /// from a previous declaration. Def will be set to the VarDecl that /// contains the initializer, and the result will be that diff --git a/lib/AST/Decl.cpp b/lib/AST/Decl.cpp index 20fe39d0af..6c620713f7 100644 --- a/lib/AST/Decl.cpp +++ b/lib/AST/Decl.cpp @@ -89,6 +89,15 @@ QualType ParmVarDecl::getOriginalType() const { return getType(); } +void VarDecl::setInit(ASTContext &C, Expr *I) { + if (EvaluatedStmt *Eval = Init.dyn_cast()) { + Eval->~EvaluatedStmt(); + C.Deallocate(Eval); + } + + Init = I; + } + bool VarDecl::isExternC(ASTContext &Context) const { if (!Context.getLangOptions().CPlusPlus) return (getDeclContext()->isTranslationUnit() && @@ -287,8 +296,13 @@ VarDecl *VarDecl::Create(ASTContext &C, DeclContext *DC, SourceLocation L, void VarDecl::Destroy(ASTContext& C) { Expr *Init = getInit(); - if (Init) + if (Init) { Init->Destroy(C); + if (EvaluatedStmt *Eval = this->Init.dyn_cast()) { + Eval->~EvaluatedStmt(); + C.Deallocate(Eval); + } + } this->~VarDecl(); C.Deallocate((void *)this); } diff --git a/lib/AST/Expr.cpp b/lib/AST/Expr.cpp index 6711faffe7..aca5efeb16 100644 --- a/lib/AST/Expr.cpp +++ b/lib/AST/Expr.cpp @@ -1210,8 +1210,21 @@ static ICEDiag CheckICE(const Expr* E, ASTContext &Ctx) { // type initialized by an ICE can be used in ICEs. if (const VarDecl *Dcl = dyn_cast(cast(E)->getDecl())) { - if (const Expr *Init = Dcl->getInit()) - return CheckICE(Init, Ctx); + if (Dcl->isInitKnownICE()) { + // We have already checked whether this subexpression is an + // integral constant expression. + if (Dcl->isInitICE()) + return NoDiag(); + else + return ICEDiag(2, E->getLocStart()); + } + + if (const Expr *Init = Dcl->getInit()) { + ICEDiag Result = CheckICE(Init, Ctx); + // Cache the result of the ICE test. + Dcl->setInitKnownICE(Ctx, Result.Val == 0); + return Result; + } } } return ICEDiag(2, E->getLocStart()); diff --git a/lib/AST/ExprConstant.cpp b/lib/AST/ExprConstant.cpp index 34b0187970..7651884aa6 100644 --- a/lib/AST/ExprConstant.cpp +++ b/lib/AST/ExprConstant.cpp @@ -700,8 +700,17 @@ bool IntExprEvaluator::VisitDeclRefExpr(const DeclRefExpr *E) { // In C, they can also be folded, although they are not ICEs. if (E->getType().getCVRQualifiers() == QualType::Const) { if (const VarDecl *D = dyn_cast(E->getDecl())) { - if (const Expr *Init = D->getInit()) - return Visit(const_cast(Init)); + if (APValue *V = D->getEvaluatedValue()) + return Success(V->getInt(), E); + if (const Expr *Init = D->getInit()) { + if (Visit(const_cast(Init))) { + // Cache the evaluated value in the variable declaration. + D->setEvaluatedValue(Info.Ctx, Result); + return true; + } + + return false; + } } } diff --git a/lib/AST/StmtIterator.cpp b/lib/AST/StmtIterator.cpp index 20024f513f..5c22e28894 100644 --- a/lib/AST/StmtIterator.cpp +++ b/lib/AST/StmtIterator.cpp @@ -140,14 +140,14 @@ Stmt*& StmtIteratorBase::GetDeclExpr() const { if (inDeclGroup()) { VarDecl* VD = cast(*DGI); - return VD->Init; + return *VD->getInitAddress(); } assert (inDecl()); if (VarDecl* VD = dyn_cast(decl)) { assert (VD->Init); - return VD->Init; + return *VD->getInitAddress(); } EnumConstantDecl* ECD = cast(decl); diff --git a/lib/Frontend/PCHReaderDecl.cpp b/lib/Frontend/PCHReaderDecl.cpp index 7d4c634193..adf0d1155e 100644 --- a/lib/Frontend/PCHReaderDecl.cpp +++ b/lib/Frontend/PCHReaderDecl.cpp @@ -342,7 +342,7 @@ void PCHDeclReader::VisitVarDecl(VarDecl *VD) { cast_or_null(Reader.GetDecl(Record[Idx++]))); VD->setTypeSpecStartLoc(SourceLocation::getFromRawEncoding(Record[Idx++])); if (Record[Idx++]) - VD->setInit(Reader.ReadDeclExpr()); + VD->setInit(*Reader.getContext(), Reader.ReadDeclExpr()); } void PCHDeclReader::VisitImplicitParamDecl(ImplicitParamDecl *PD) { diff --git a/lib/Sema/SemaDecl.cpp b/lib/Sema/SemaDecl.cpp index 22bdc7999b..4149fa4c9a 100644 --- a/lib/Sema/SemaDecl.cpp +++ b/lib/Sema/SemaDecl.cpp @@ -2581,7 +2581,7 @@ void Sema::AddInitializerToDecl(DeclPtrTy dcl, ExprArg init, bool DirectInit) { // }; // Attach the initializer - VDecl->setInit(Init); + VDecl->setInit(Context, Init); // C++ [class.mem]p4: // A member-declarator can contain a constant-initializer only @@ -2644,7 +2644,7 @@ void Sema::AddInitializerToDecl(DeclPtrTy dcl, ExprArg init, bool DirectInit) { } // Attach the initializer to the decl. - VDecl->setInit(Init); + VDecl->setInit(Context, Init); // If the previous declaration of VDecl was a tentative definition, // remove it from the set of tentative definitions. diff --git a/lib/Sema/SemaDeclCXX.cpp b/lib/Sema/SemaDeclCXX.cpp index feb94569ed..ebe34064d6 100644 --- a/lib/Sema/SemaDeclCXX.cpp +++ b/lib/Sema/SemaDeclCXX.cpp @@ -1776,7 +1776,7 @@ void Sema::InitializeVarWithConstructor(VarDecl *VD, Expr **Exprs, unsigned NumExprs) { Expr *Temp = CXXConstructExpr::Create(Context, VD, DeclInitType, Constructor, false, Exprs, NumExprs); - VD->setInit(Temp); + VD->setInit(Context, Temp); } /// AddCXXDirectInitializerToDecl - This action is called immediately after -- 2.40.0