diff --git a/clang/include/clang/AST/ASTContext.h b/clang/include/clang/AST/ASTContext.h --- a/clang/include/clang/AST/ASTContext.h +++ b/clang/include/clang/AST/ASTContext.h @@ -139,6 +139,12 @@ } // namespace comments +namespace interp { + +class Context; + +} // namespace interp + struct TypeInfo { uint64_t Width = 0; unsigned Align = 0; @@ -564,6 +570,7 @@ const TargetInfo *Target = nullptr; const TargetInfo *AuxTarget = nullptr; clang::PrintingPolicy PrintingPolicy; + std::unique_ptr InterpContext; public: IdentifierTable &Idents; @@ -573,6 +580,9 @@ IntrusiveRefCntPtr ExternalSource; ASTMutationListener *Listener = nullptr; + /// Returns the clang bytecode interpreter context. + interp::Context &getInterpContext(); + /// Container for either a single DynTypedNode or for an ArrayRef to /// DynTypedNode. For use with ParentMap. class DynTypedNodeList { diff --git a/clang/include/clang/Basic/DiagnosticASTKinds.td b/clang/include/clang/Basic/DiagnosticASTKinds.td --- a/clang/include/clang/Basic/DiagnosticASTKinds.td +++ b/clang/include/clang/Basic/DiagnosticASTKinds.td @@ -228,6 +228,8 @@ def note_constexpr_bit_cast_indet_dest : Note< "indeterminate value can only initialize an object of type 'unsigned char'" "%select{, 'char',|}1 or 'std::byte'; %0 is invalid">; +def err_experimental_clang_interp_failed : Error< + "the experimental clang interpreter failed to evaluate an expression">; def warn_integer_constant_overflow : Warning< "overflow in expression; result is %0 with type %1">, diff --git a/clang/include/clang/Basic/LangOptions.def b/clang/include/clang/Basic/LangOptions.def --- a/clang/include/clang/Basic/LangOptions.def +++ b/clang/include/clang/Basic/LangOptions.def @@ -288,6 +288,10 @@ "maximum constexpr call depth") BENIGN_LANGOPT(ConstexprStepLimit, 32, 1048576, "maximum constexpr evaluation steps") +BENIGN_LANGOPT(EnableClangInterp, 1, 0, + "enable the experimental clang interpreter") +BENIGN_LANGOPT(ForceClangInterp, 1, 0, + "force the use of the experimental constexpr interpreter") BENIGN_LANGOPT(BracketDepth, 32, 256, "maximum bracket nesting depth") BENIGN_LANGOPT(NumLargeByValueCopy, 32, 0, diff --git a/clang/include/clang/Basic/OptionalDiagnostic.h b/clang/include/clang/Basic/OptionalDiagnostic.h new file mode 100644 --- /dev/null +++ b/clang/include/clang/Basic/OptionalDiagnostic.h @@ -0,0 +1,78 @@ +//===- OptionalDiagnostic.h - An optional diagnostic ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +/// \file +/// Implements a partial diagnostic which may not be emitted. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_BASIC_OPTIONALDIAGNOSTIC_H +#define LLVM_CLANG_BASIC_OPTIONALDIAGNOSTIC_H + +#include "clang/AST/APValue.h" +#include "clang/Basic/PartialDiagnostic.h" +#include "llvm/ADT/APFloat.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" + +namespace clang { + +/// A partial diagnostic which we might know in advance that we are not going +/// to emit. +class OptionalDiagnostic { + PartialDiagnostic *Diag; + +public: + explicit OptionalDiagnostic(PartialDiagnostic *Diag = nullptr) : Diag(Diag) {} + + template OptionalDiagnostic &operator<<(const T &v) { + if (Diag) + *Diag << v; + return *this; + } + + OptionalDiagnostic &operator<<(const llvm::APSInt &I) { + if (Diag) { + SmallVector Buffer; + I.toString(Buffer); + *Diag << StringRef(Buffer.data(), Buffer.size()); + } + return *this; + } + + OptionalDiagnostic &operator<<(const llvm::APFloat &F) { + if (Diag) { + // FIXME: Force the precision of the source value down so we don't + // print digits which are usually useless (we don't really care here if + // we truncate a digit by accident in edge cases). Ideally, + // APFloat::toString would automatically print the shortest + // representation which rounds to the correct value, but it's a bit + // tricky to implement. Could use std::to_chars. + unsigned precision = llvm::APFloat::semanticsPrecision(F.getSemantics()); + precision = (precision * 59 + 195) / 196; + SmallVector Buffer; + F.toString(Buffer, precision); + *Diag << StringRef(Buffer.data(), Buffer.size()); + } + return *this; + } + + OptionalDiagnostic &operator<<(const APFixedPoint &FX) { + if (Diag) { + SmallVector Buffer; + FX.toString(Buffer); + *Diag << StringRef(Buffer.data(), Buffer.size()); + } + return *this; + } +}; + +} // namespace clang + +#endif diff --git a/clang/include/clang/Driver/Options.td b/clang/include/clang/Driver/Options.td --- a/clang/include/clang/Driver/Options.td +++ b/clang/include/clang/Driver/Options.td @@ -833,6 +833,10 @@ def fconstant_string_class_EQ : Joined<["-"], "fconstant-string-class=">, Group; def fconstexpr_depth_EQ : Joined<["-"], "fconstexpr-depth=">, Group; def fconstexpr_steps_EQ : Joined<["-"], "fconstexpr-steps=">, Group; +def fexperimental_clang_interpreter : Flag<["-"], "fexperimental-clang-interpreter">, Group, + HelpText<"Enable the experimental clang interpreter">, Flags<[CC1Option]>; +def fforce_experimental_clang_interpreter : Flag<["-"], "fforce-experimental-clang-interpreter">, Group, + HelpText<"Force the use of the experimental clang interpreter, failing on missing features">, Flags<[CC1Option]>; def fconstexpr_backtrace_limit_EQ : Joined<["-"], "fconstexpr-backtrace-limit=">, Group; def fno_crash_diagnostics : Flag<["-"], "fno-crash-diagnostics">, Group, Flags<[NoArgumentUnused, CoreOption]>, diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp --- a/clang/lib/AST/ASTContext.cpp +++ b/clang/lib/AST/ASTContext.cpp @@ -12,6 +12,7 @@ #include "clang/AST/ASTContext.h" #include "CXXABI.h" +#include "Interp/Context.h" #include "clang/AST/APValue.h" #include "clang/AST/ASTMutationListener.h" #include "clang/AST/ASTTypeTraits.h" @@ -737,6 +738,13 @@ llvm_unreachable("Invalid CXXABI type!"); } +interp::Context &ASTContext::getInterpContext() { + if (!InterpContext) { + InterpContext.reset(new interp::Context(*this)); + } + return *InterpContext.get(); +} + static const LangASMap *getAddressSpaceMap(const TargetInfo &T, const LangOptions &LOpts) { if (LOpts.FakeAddressSpaceMap) { diff --git a/clang/lib/AST/CMakeLists.txt b/clang/lib/AST/CMakeLists.txt --- a/clang/lib/AST/CMakeLists.txt +++ b/clang/lib/AST/CMakeLists.txt @@ -4,6 +4,8 @@ Support ) +add_subdirectory(Interp) + add_clang_library(clangAST APValue.cpp ASTConsumer.cpp @@ -80,6 +82,7 @@ VTTBuilder.cpp LINK_LIBS + clangInterp clangBasic clangLex ) diff --git a/clang/lib/AST/ExprConstant.cpp b/clang/lib/AST/ExprConstant.cpp --- a/clang/lib/AST/ExprConstant.cpp +++ b/clang/lib/AST/ExprConstant.cpp @@ -32,13 +32,16 @@ // //===----------------------------------------------------------------------===// +#include "Interp/Context.h" +#include "Interp/Frame.h" +#include "Interp/State.h" #include "clang/AST/APValue.h" #include "clang/AST/ASTContext.h" #include "clang/AST/ASTDiagnostic.h" #include "clang/AST/ASTLambda.h" +#include "clang/AST/CXXInheritance.h" #include "clang/AST/CharUnits.h" #include "clang/AST/CurrentSourceLocExprScope.h" -#include "clang/AST/CXXInheritance.h" #include "clang/AST/Expr.h" #include "clang/AST/OSLog.h" #include "clang/AST/RecordLayout.h" @@ -49,6 +52,8 @@ #include "clang/Basic/TargetInfo.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallBitVector.h" +#include "clang/Basic/OptionalDiagnostic.h" +#include "clang/Basic/TargetInfo.h" #include "llvm/Support/SaveAndRestore.h" #include "llvm/Support/raw_ostream.h" #include @@ -66,8 +71,8 @@ namespace { struct LValue; - struct CallStackFrame; - struct EvalInfo; + class CallStackFrame; + class EvalInfo; using SourceLocExprScopeGuard = CurrentSourceLocExprScope::SourceLocExprScopeGuard; @@ -222,12 +227,6 @@ return MostDerivedLength; } - // The order of this enum is important for diagnostics. - enum CheckSubobjectKind { - CSK_Base, CSK_Derived, CSK_Field, CSK_ArrayToPointer, CSK_ArrayIndex, - CSK_Real, CSK_Imag - }; - /// A path from a glvalue to a subobject of that glvalue. struct SubobjectDesignator { /// True if the subobject was named in a manner not supported by C++11. Such @@ -480,7 +479,8 @@ }; /// A stack frame in the constexpr call stack. - struct CallStackFrame { + class CallStackFrame : public interp::Frame { + public: EvalInfo &Info; /// Parent - The caller of this stack frame. @@ -574,6 +574,12 @@ } APValue &createTemporary(const void *Key, bool IsLifetimeExtended); + + void describe(llvm::raw_ostream &OS) override; + + Frame *getCaller() const override { return Caller; } + SourceLocation getCallLocation() const override { return CallLoc; } + const FunctionDecl *getCallee() const override { return Callee; } }; /// Temporarily override 'this'. @@ -592,59 +598,6 @@ const LValue *OldThis; }; - /// A partial diagnostic which we might know in advance that we are not going - /// to emit. - class OptionalDiagnostic { - PartialDiagnostic *Diag; - - public: - explicit OptionalDiagnostic(PartialDiagnostic *Diag = nullptr) - : Diag(Diag) {} - - template - OptionalDiagnostic &operator<<(const T &v) { - if (Diag) - *Diag << v; - return *this; - } - - OptionalDiagnostic &operator<<(const APSInt &I) { - if (Diag) { - SmallVector Buffer; - I.toString(Buffer); - *Diag << StringRef(Buffer.data(), Buffer.size()); - } - return *this; - } - - OptionalDiagnostic &operator<<(const APFloat &F) { - if (Diag) { - // FIXME: Force the precision of the source value down so we don't - // print digits which are usually useless (we don't really care here if - // we truncate a digit by accident in edge cases). Ideally, - // APFloat::toString would automatically print the shortest - // representation which rounds to the correct value, but it's a bit - // tricky to implement. - unsigned precision = - llvm::APFloat::semanticsPrecision(F.getSemantics()); - precision = (precision * 59 + 195) / 196; - SmallVector Buffer; - F.toString(Buffer, precision); - *Diag << StringRef(Buffer.data(), Buffer.size()); - } - return *this; - } - - OptionalDiagnostic &operator<<(const APFixedPoint &FX) { - if (Diag) { - SmallVector Buffer; - FX.toString(Buffer); - *Diag << StringRef(Buffer.data(), Buffer.size()); - } - return *this; - } - }; - /// A cleanup, and a flag indicating whether it is lifetime-extended. class Cleanup { llvm::PointerIntPair Value; @@ -707,7 +660,8 @@ /// rules. For example, the RHS of (0 && foo()) is not evaluated. We can /// evaluate the expression regardless of what the RHS is, but C only allows /// certain things in certain situations. - struct EvalInfo { + class EvalInfo : public interp::State { + public: ASTContext &Ctx; /// EvalStatus - Contains information about the evaluation. @@ -727,6 +681,13 @@ /// we will evaluate. unsigned StepsLeft; + /// Force the use of the constexpr interpreter, bailing out with an error + /// if a feature is unsupported. + bool ForceClangInterp; + + /// Enable the experimental clang interpreter. + bool EnableClangInterp; + /// BottomFrame - The frame in which evaluation started. This must be /// initialized after CurrentCall and CallStackDepth. CallStackFrame BottomFrame; @@ -837,7 +798,7 @@ /// Are we checking whether the expression is a potential constant /// expression? - bool checkingPotentialConstantExpression() const { + bool checkingPotentialConstantExpression() const override { return EvalMode == EM_PotentialConstantExpression || EvalMode == EM_PotentialConstantExpressionUnevaluated; } @@ -845,12 +806,16 @@ /// Are we checking an expression for overflow? // FIXME: We should check for any kind of undefined or suspicious behavior // in such constructs, not just overflow. - bool checkingForOverflow() { return EvalMode == EM_EvaluateForOverflow; } + bool checkingForOverflow() const override { + return EvalMode == EM_EvaluateForOverflow; + } EvalInfo(const ASTContext &C, Expr::EvalStatus &S, EvaluationMode Mode) : Ctx(const_cast(C)), EvalStatus(S), CurrentCall(nullptr), CallStackDepth(0), NextCallIndex(1), StepsLeft(getLangOpts().ConstexprStepLimit), + ForceClangInterp(getLangOpts().ForceClangInterp), + EnableClangInterp(ForceClangInterp || getLangOpts().EnableClangInterp), BottomFrame(*this, SourceLocation(), nullptr, nullptr, nullptr), EvaluatingDecl((const ValueDecl *)nullptr), EvaluatingDeclValue(nullptr), HasActiveDiagnostic(false), @@ -862,8 +827,6 @@ EvaluatingDeclValue = &Value; } - const LangOptions &getLangOpts() const { return Ctx.getLangOpts(); } - bool CheckCallLimit(SourceLocation Loc) { // Don't perform any constexpr calls (other than the call we're checking) // when checking a potential constant expression. @@ -907,118 +870,52 @@ } private: - /// Add a diagnostic to the diagnostics list. - PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId) { - PartialDiagnostic PD(DiagId, Ctx.getDiagAllocator()); - EvalStatus.Diag->push_back(std::make_pair(Loc, PD)); - return EvalStatus.Diag->back().second; - } - - /// Add notes containing a call stack to the current point of evaluation. - void addCallStack(unsigned Limit); - - private: - OptionalDiagnostic Diag(SourceLocation Loc, diag::kind DiagId, - unsigned ExtraNotes, bool IsCCEDiag) { - - if (EvalStatus.Diag) { - // If we have a prior diagnostic, it will be noting that the expression - // isn't a constant expression. This diagnostic is more important, - // unless we require this evaluation to produce a constant expression. - // - // FIXME: We might want to show both diagnostics to the user in - // EM_ConstantFold mode. - if (!EvalStatus.Diag->empty()) { - switch (EvalMode) { - case EM_ConstantFold: - case EM_IgnoreSideEffects: - case EM_EvaluateForOverflow: - if (!HasFoldFailureDiagnostic) - break; - // We've already failed to fold something. Keep that diagnostic. - LLVM_FALLTHROUGH; - case EM_ConstantExpression: - case EM_PotentialConstantExpression: - case EM_ConstantExpressionUnevaluated: - case EM_PotentialConstantExpressionUnevaluated: - HasActiveDiagnostic = false; - return OptionalDiagnostic(); - } + interp::Frame *getCurrentFrame() override { return CurrentCall; } + const interp::Frame *getBottomFrame() const override { return &BottomFrame; } + + bool hasActiveDiagnostic() override { return HasActiveDiagnostic; } + void setActiveDiagnostic(bool Flag) override { HasActiveDiagnostic = Flag; } + + void setFoldFailureDiagnostic(bool Flag) override { + HasFoldFailureDiagnostic = Flag; + } + + Expr::EvalStatus &getEvalStatus() const override { return EvalStatus; } + + ASTContext &getCtx() const override { return Ctx; } + + // If we have a prior diagnostic, it will be noting that the expression + // isn't a constant expression. This diagnostic is more important, + // unless we require this evaluation to produce a constant expression. + // + // FIXME: We might want to show both diagnostics to the user in + // EM_ConstantFold mode. + bool hasPriorDiagnostic() override { + if (!EvalStatus.Diag->empty()) { + switch (EvalMode) { + case EM_ConstantFold: + case EM_IgnoreSideEffects: + case EM_EvaluateForOverflow: + if (!HasFoldFailureDiagnostic) + break; + // We've already failed to fold something. Keep that diagnostic. + LLVM_FALLTHROUGH; + case EM_ConstantExpression: + case EM_PotentialConstantExpression: + case EM_ConstantExpressionUnevaluated: + case EM_PotentialConstantExpressionUnevaluated: + setActiveDiagnostic(false); + return true; } - - unsigned CallStackNotes = CallStackDepth - 1; - unsigned Limit = Ctx.getDiagnostics().getConstexprBacktraceLimit(); - if (Limit) - CallStackNotes = std::min(CallStackNotes, Limit + 1); - if (checkingPotentialConstantExpression()) - CallStackNotes = 0; - - HasActiveDiagnostic = true; - HasFoldFailureDiagnostic = !IsCCEDiag; - EvalStatus.Diag->clear(); - EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes); - addDiag(Loc, DiagId); - if (!checkingPotentialConstantExpression()) - addCallStack(Limit); - return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second); } - HasActiveDiagnostic = false; - return OptionalDiagnostic(); - } - public: - // Diagnose that the evaluation could not be folded (FF => FoldFailure) - OptionalDiagnostic - FFDiag(SourceLocation Loc, - diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, - unsigned ExtraNotes = 0) { - return Diag(Loc, DiagId, ExtraNotes, false); - } - - OptionalDiagnostic FFDiag(const Expr *E, diag::kind DiagId - = diag::note_invalid_subexpr_in_const_expr, - unsigned ExtraNotes = 0) { - if (EvalStatus.Diag) - return Diag(E->getExprLoc(), DiagId, ExtraNotes, /*IsCCEDiag*/false); - HasActiveDiagnostic = false; - return OptionalDiagnostic(); - } - - /// Diagnose that the evaluation does not produce a C++11 core constant - /// expression. - /// - /// FIXME: Stop evaluating if we're in EM_ConstantExpression or - /// EM_PotentialConstantExpression mode and we produce one of these. - OptionalDiagnostic CCEDiag(SourceLocation Loc, diag::kind DiagId - = diag::note_invalid_subexpr_in_const_expr, - unsigned ExtraNotes = 0) { - // Don't override a previous diagnostic. Don't bother collecting - // diagnostics if we're evaluating for overflow. - if (!EvalStatus.Diag || !EvalStatus.Diag->empty()) { - HasActiveDiagnostic = false; - return OptionalDiagnostic(); - } - return Diag(Loc, DiagId, ExtraNotes, true); - } - OptionalDiagnostic CCEDiag(const Expr *E, diag::kind DiagId - = diag::note_invalid_subexpr_in_const_expr, - unsigned ExtraNotes = 0) { - return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes); - } - /// Add a note to a prior diagnostic. - OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId) { - if (!HasActiveDiagnostic) - return OptionalDiagnostic(); - return OptionalDiagnostic(&addDiag(Loc, DiagId)); + return false; } - /// Add a stack of notes to a prior diagnostic. - void addNotes(ArrayRef Diags) { - if (HasActiveDiagnostic) { - EvalStatus.Diag->insert(EvalStatus.Diag->end(), - Diags.begin(), Diags.end()); - } + unsigned getCallStackDepth() override { + return CallStackDepth; } + public: /// Should we continue evaluation after encountering a side-effect that we /// couldn't model? bool keepEvaluatingAfterSideEffect() { @@ -1064,7 +961,7 @@ /// Note that we hit something that was technically undefined behavior, but /// that we can evaluate past it (such as signed overflow or floating-point /// division by zero.) - bool noteUndefinedBehavior() { + bool noteUndefinedBehavior() override { EvalStatus.HasUndefinedBehavior = true; return keepEvaluatingAfterUndefinedBehavior(); } @@ -1321,62 +1218,6 @@ return Result; } -static void describeCall(CallStackFrame *Frame, raw_ostream &Out); - -void EvalInfo::addCallStack(unsigned Limit) { - // Determine which calls to skip, if any. - unsigned ActiveCalls = CallStackDepth - 1; - unsigned SkipStart = ActiveCalls, SkipEnd = SkipStart; - if (Limit && Limit < ActiveCalls) { - SkipStart = Limit / 2 + Limit % 2; - SkipEnd = ActiveCalls - Limit / 2; - } - - // Walk the call stack and add the diagnostics. - unsigned CallIdx = 0; - for (CallStackFrame *Frame = CurrentCall; Frame != &BottomFrame; - Frame = Frame->Caller, ++CallIdx) { - // Skip this call? - if (CallIdx >= SkipStart && CallIdx < SkipEnd) { - if (CallIdx == SkipStart) { - // Note that we're skipping calls. - addDiag(Frame->CallLoc, diag::note_constexpr_calls_suppressed) - << unsigned(ActiveCalls - Limit); - } - continue; - } - - // Use a different note for an inheriting constructor, because from the - // user's perspective it's not really a function at all. - if (auto *CD = dyn_cast_or_null(Frame->Callee)) { - if (CD->isInheritingConstructor()) { - addDiag(Frame->CallLoc, diag::note_constexpr_inherited_ctor_call_here) - << CD->getParent(); - continue; - } - } - - SmallVector 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. Note that -/// we consider a member function call to be a kind of access, even though -/// it is not formally an access of the object, because it has (largely) the -/// same set of semantic restrictions. -enum AccessKinds { - AK_Read, - AK_Assign, - AK_Increment, - AK_Decrement, - AK_MemberCall, - AK_DynamicCast, - AK_TypeId, -}; - static bool isModification(AccessKinds AK) { switch (AK) { case AK_Read: @@ -1744,36 +1585,36 @@ } /// Produce a string describing the given constexpr call. -static void describeCall(CallStackFrame *Frame, raw_ostream &Out) { +void CallStackFrame::describe(raw_ostream &Out) { unsigned ArgIndex = 0; - bool IsMemberCall = isa(Frame->Callee) && - !isa(Frame->Callee) && - cast(Frame->Callee)->isInstance(); + bool IsMemberCall = isa(Callee) && + !isa(Callee) && + cast(Callee)->isInstance(); if (!IsMemberCall) - Out << *Frame->Callee << '('; + Out << *Callee << '('; - if (Frame->This && IsMemberCall) { + if (This && IsMemberCall) { APValue Val; - Frame->This->moveInto(Val); - Val.printPretty(Out, Frame->Info.Ctx, - Frame->This->Designator.MostDerivedType); + This->moveInto(Val); + Val.printPretty(Out, Info.Ctx, + This->Designator.MostDerivedType); // FIXME: Add parens around Val if needed. - Out << "->" << *Frame->Callee << '('; + Out << "->" << *Callee << '('; IsMemberCall = false; } - for (FunctionDecl::param_const_iterator I = Frame->Callee->param_begin(), - E = Frame->Callee->param_end(); I != E; ++I, ++ArgIndex) { + for (FunctionDecl::param_const_iterator I = Callee->param_begin(), + E = Callee->param_end(); I != E; ++I, ++ArgIndex) { if (ArgIndex > (unsigned)IsMemberCall) Out << ", "; const ParmVarDecl *Param = *I; - const APValue &Arg = Frame->Arguments[ArgIndex]; - Arg.printPretty(Out, Frame->Info.Ctx, Param->getType()); + const APValue &Arg = Arguments[ArgIndex]; + Arg.printPretty(Out, Info.Ctx, Param->getType()); if (ArgIndex == 0 && IsMemberCall) - Out << "->" << *Frame->Callee << '('; + Out << "->" << *Callee << '('; } Out << ')'; @@ -5189,6 +5030,19 @@ Frame.LambdaThisCaptureField); } + // Try to evaluate the function call in the bytecode VM. + if (Info.EnableClangInterp) { + auto &InterpCtx = Info.Ctx.getInterpContext(); + switch (InterpCtx.handleFunctionCall(Info, Callee, ArgValues, Result)) { + case interp::InterpResult::Success: + return true; + case interp::InterpResult::Fail: + return false; + case interp::InterpResult::Bail: + break; + } + } + StmtResult Ret = {Result, ResultSlot}; EvalStmtResult ESR = EvaluateStmt(Ret, Info, Body); if (ESR == ESR_Succeeded) { @@ -12273,6 +12127,18 @@ /// EvaluateAsRValue - Try to evaluate this expression, performing an implicit /// lvalue-to-rvalue cast if it is an lvalue. static bool EvaluateAsRValue(EvalInfo &Info, const Expr *E, APValue &Result) { + if (Info.EnableClangInterp) { + auto &InterpCtx = Info.Ctx.getInterpContext(); + switch (InterpCtx.evaluateAsRValue(Info, E, Result)) { + case interp::InterpResult::Success: + return true; + case interp::InterpResult::Fail: + return false; + case interp::InterpResult::Bail: + break; + } + } + if (E->getType().isNull()) return false; @@ -12480,11 +12346,28 @@ Expr::EvalStatus EStatus; EStatus.Diag = &Notes; - EvalInfo InitInfo(Ctx, EStatus, VD->isConstexpr() + EvalInfo Info(Ctx, EStatus, VD->isConstexpr() ? EvalInfo::EM_ConstantExpression : EvalInfo::EM_ConstantFold); - InitInfo.setEvaluatingDecl(VD, Value); - InitInfo.InConstantContext = true; + Info.setEvaluatingDecl(VD, Value); + Info.InConstantContext = true; + + if (Info.EnableClangInterp) { + auto &InterpCtx = const_cast(Ctx).getInterpContext(); + switch (InterpCtx.evaluateAsInitializer(Info, VD, Value)) { + case interp::InterpResult::Fail: + // Bail out if an error was encountered. + return false; + case interp::InterpResult::Success: + // If the interpreter is forced, do not compute any other value. + if (Info.ForceClangInterp) + return true; + break; + case interp::InterpResult::Bail: + // Evaluate the value again for the tree evaluator to use. + break; + } + } LValue LVal; LVal.set(VD); @@ -12496,18 +12379,17 @@ if (Ctx.getLangOpts().CPlusPlus && !VD->hasLocalStorage() && !VD->getType()->isReferenceType()) { ImplicitValueInitExpr VIE(VD->getType()); - if (!EvaluateInPlace(Value, InitInfo, LVal, &VIE, + if (!EvaluateInPlace(Value, Info, LVal, &VIE, /*AllowNonLiteralTypes=*/true)) return false; } - if (!EvaluateInPlace(Value, InitInfo, LVal, this, + if (!EvaluateInPlace(Value, Info, LVal, this, /*AllowNonLiteralTypes=*/true) || EStatus.HasSideEffects) return false; - return CheckConstantExpression(InitInfo, VD->getLocation(), VD->getType(), - Value); + return CheckConstantExpression(Info, VD->getLocation(), VD->getType(), Value); } /// isEvaluatable - Call EvaluateAsRValue to see if this expression can be @@ -13182,6 +13064,18 @@ EvalInfo::EM_PotentialConstantExpression); Info.InConstantContext = true; + // The constexpr VM attempts to compile all methods to bytecode here. + if (Info.EnableClangInterp) { + auto &InterpCtx = Info.Ctx.getInterpContext(); + switch (InterpCtx.isPotentialConstantExpr(Info, FD)) { + case interp::InterpResult::Success: + case interp::InterpResult::Fail: + return Diags.empty(); + case interp::InterpResult::Bail: + break; + } + } + const CXXMethodDecl *MD = dyn_cast(FD); const CXXRecordDecl *RD = MD ? MD->getParent()->getCanonicalDecl() : nullptr; diff --git a/clang/lib/AST/Interp/ByteCodeGen.h b/clang/lib/AST/Interp/ByteCodeGen.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeGen.h @@ -0,0 +1,164 @@ +//===--- ByteCodeGen.h - Code Generator for the constexpr VM -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the constexpr bytecode compiler. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_BYTECODEGEN_H +#define LLVM_CLANG_AST_INTERP_BYTECODEGEN_H + +#include "EvalEmitter.h" +#include "LinkEmitter.h" +#include "Pointer.h" +#include "Type.h" +#include "clang/AST/Decl.h" +#include "clang/AST/StmtVisitor.h" +#include "llvm/ADT/Optional.h" + +namespace clang { +class QualType; + +namespace interp { +class Function; +class State; + +template class LocalScope; +template class LoopScope; +template class SwitchScope; +template class RecordScope; +template class CompilerScope; + +/// Compilation context for a constexpr function. +template +class ByteCodeGen : public ConstStmtVisitor, bool>, + public Emitter { + using NullaryFn = bool (ByteCodeGen::*)(const SourceInfo &); + using UnaryFn = bool (ByteCodeGen::*)(PrimType, const SourceInfo &); + using BinaryFn = bool (ByteCodeGen::*)(PrimType, PrimType, const SourceInfo &); + + using LabelTy = typename Emitter::LabelTy; + using OptLabelTy = llvm::Optional; + using CaseMap = llvm::DenseMap; + + using AddrTy = typename Emitter::AddrTy; + + /// Current compilation context. + Context &Ctx; + /// Evaluation state. + State &S; + /// Program to link to. + Program &P; + +public: + /// Initializes the compiler and the backend emitter. + template + ByteCodeGen(Context &Ctx, State &S, Program &P, Tys &&... Args) + : Emitter(Ctx, S, P, Args...), Ctx(Ctx), S(S), P(P) {} + + // Expression visitors - result returned on stack. + bool VisitDeclRefExpr(const DeclRefExpr *E); + bool VisitCastExpr(const CastExpr *CE); + bool VisitIntegerLiteral(const IntegerLiteral *E); + bool VisitParenExpr(const ParenExpr *PE); + bool VisitBinaryOperator(const BinaryOperator *BO); + + // If an unsupported construct is encountered, no code is generated. + bool VisitExpr(const Expr *E) { return this->bail(E); } + bool VisitStmt(const Stmt *S) { llvm_unreachable("not compiled"); } + +private: + // Statement visitors. + bool visit(const Stmt *S); + bool visitCompoundStmt(const CompoundStmt *S); + bool visitDeclStmt(const DeclStmt *DS); + bool visitReturnStmt(const ReturnStmt *RS); + bool visitIfStmt(const IfStmt *IS); + + /// Evaluates an expr for side effects and discards the result. + bool discard(const Expr *E); + bool discardBinaryOperator(const BinaryOperator *BO); + + enum class AccessKind { + /// Value is read and pushed to stack. + Read, + /// Direct method generates a value which is written. Returns pointer. + Write, + /// Direct method generates a value which is written. + WriteVoid, + /// Direct method receives the value, pushes mutated value. Returns pointer. + ReadWrite, + /// Direct method receives the value, pushes mutated copy. + ReadWriteVoid + }; + + /// Method to directly load a value. If the value can be fetched directly, + /// the direct handler is called. Otherwise, a pointer is left on the stack + /// and the indirect handler is expected to operate on that. + bool dereference(const Expr *LValue, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + + /// Compiles a variable declaration. + bool visitVarDecl(const VarDecl *VD); + +protected: + virtual bool compile(const FunctionDecl *F) override; + virtual bool compile(const Expr *E) override; + virtual bool compile(const VarDecl *VD) override; + +private: + friend class CompilerScope; + friend class LocalScope; + friend class RecordScope; + friend class LoopScope; + friend class SwitchScope; + + /// Returns the size int bits of an integer. + unsigned getIntWidth(QualType Ty) { + auto &ASTContext = Ctx.getASTContext(); + return ASTContext.getIntWidth(Ty); + } + + /// Emits an APInt constant. + bool emitConst(PrimType T, unsigned NumBits, const llvm::APInt &Value, + const Expr *E); + + /// Emits an integer constant. + template + bool emitConst(const Expr *E, T Value) { + QualType Ty = E->getType(); + unsigned NumBits = getIntWidth(Ty); + APInt WrappedValue(NumBits, Value, std::is_signed::value); + return emitConst(*Ctx.classify(Ty), NumBits, WrappedValue, E); + } + + /// Creates a local primitive value. + unsigned allocateLocalPrimitive(DeclTy &&Decl, PrimType Ty, bool IsMutable, + bool IsExtended = false); + + /// Compiles an argument. + bool visitArgument(const Expr *E); + + /// Returns or compiles a function. + Function *getFunction(const FunctionDecl *FD); + + /// Variable to storage mapping. + llvm::DenseMap Locals; + + /// Current scope. + CompilerScope *Top = nullptr; +}; + +extern template class ByteCodeGen; +extern template class ByteCodeGen; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/ByteCodeGen.cpp b/clang/lib/AST/Interp/ByteCodeGen.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeGen.cpp @@ -0,0 +1,749 @@ +//===--- ByteCodeGen.cpp - Code Generator for the constexpr VM -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "ByteCodeGen.h" +#include "ByteCodeGenError.h" +#include "Context.h" +#include "EvalEmitter.h" +#include "Function.h" +#include "LinkEmitter.h" +#include "Opcode.h" +#include "Program.h" +#include "State.h" +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +using Error = llvm::Error; + +namespace clang { +namespace interp { + +/// Scope chain managing the compiler state. +/// +/// Classes deriving from this override certain parts of the compiler +/// state to deal with block scopes, break/continue labels and cases. +template class CompilerScope { +public: + virtual ~CompilerScope() { Ctx->Top = this->Parent; } + + void add(const Scope::Local &Local, bool IsExtended) { + if (IsExtended) + this->addExtended(Local); + else + this->addLocal(Local); + } + + virtual void addLocal(const Scope::Local &Local) { + if (this->Parent) + this->Parent->addLocal(Local); + } + + virtual void addExtended(const Scope::Local &Local) { + if (this->Parent) + this->Parent->addExtended(Local); + } + + virtual void emitDestructor() {} + + CompilerScope *getParent() { return Parent; } + +protected: + CompilerScope(ByteCodeGen *Ctx) : Ctx(Ctx), Parent(Ctx->Top) { + Ctx->Top = this; + } + + /// ByteCodeGen instance. + ByteCodeGen *Ctx; + /// Link to the parent scope. + CompilerScope *Parent; +}; + +/// Scope for local variables. +/// +/// When the scope is destroyed, instructions are emitted to tear down +/// all variables declared in this scope. +template class LocalScope : public CompilerScope { +public: + LocalScope(ByteCodeGen *Ctx) : CompilerScope(Ctx) {} + + ~LocalScope() override { this->emitDestructor(); } + + void addLocal(const Scope::Local &Local) override { + if (!Idx.hasValue()) { + Idx = this->Ctx->Descriptors.size(); + this->Ctx->Descriptors.emplace_back(); + } + + this->Ctx->Descriptors[*Idx].emplace_back(Local); + } + + void emitDestructor() override { + if (!Idx.hasValue()) + return; + this->Ctx->emitDestroy(*Idx, {}); + } + +protected: + /// Index of the scope in the chain. + llvm::Optional Idx; +}; + +template class BlockScope final : public LocalScope { +public: + BlockScope(ByteCodeGen *Ctx) : LocalScope(Ctx) {} + + void addExtended(const Scope::Local &Local) override { + llvm_unreachable("Cannot create temporaries in full scopes"); + } +}; + +/// Expression scope which tracks potentially lifetime extended +/// temporaries which are hoisted to the parent scope on exit. +template class ExprScope final : public LocalScope { +public: + ExprScope(ByteCodeGen *Ctx) : LocalScope(Ctx) {} + + void addExtended(const Scope::Local &Local) override { + this->Parent->addLocal(Local); + } +}; + +/// Scope used for toplevel declarators. +template class DeclScope final : public LocalScope { +public: + DeclScope(ByteCodeGen *Ctx) : LocalScope(Ctx) {} + + void addExtended(const Scope::Local &Local) override { + return this->addLocal(Local); + } +}; + +} // namespace interp +} // namespace clang + +template bool ByteCodeGen::visit(const Stmt *S) { + switch (S->getStmtClass()) { + case Stmt::CompoundStmtClass: + return visitCompoundStmt(cast(S)); + case Stmt::DeclStmtClass: + return visitDeclStmt(cast(S)); + case Stmt::ReturnStmtClass: + return visitReturnStmt(cast(S)); + case Stmt::IfStmtClass: + return visitIfStmt(cast(S)); + case Stmt::NullStmtClass: + return true; + default: { + if (auto *Exp = dyn_cast(S)) { + if (Exp->getType()->isVoidType()) { + return this->Visit(Exp); + } else { + return discard(Exp); + } + } else { + return this->bail(S); + } + } + } +} + +template +bool ByteCodeGen::visitCompoundStmt(const CompoundStmt *S) { + BlockScope Scope(this); + for (auto *Stmt : S->body()) + if (!visit(Stmt)) + return false; + return true; +} + +template +bool ByteCodeGen::visitDeclStmt(const DeclStmt *DS) { + for (auto *D : DS->decls()) { + // Variable declarator. + if (auto *VD = dyn_cast(D)) { + if (!visitVarDecl(VD)) + return false; + continue; + } + + // TODO: implement other declarations. + return this->bail(DS); + } + + return true; +} + +template +bool ByteCodeGen::visitReturnStmt(const ReturnStmt *RS) { + if (auto *RetExpr = RS->getRetValue()) { + ExprScope RetScope(this); + QualType RT = RetExpr->getType(); + if (Ctx.isComposite(RT)) { + // RVO - construct the value in the return location. + return this->bail(RS); + } else { + // Primitive types are simply returned. + if (auto T = Ctx.classify(RetExpr)) { + if (!this->Visit(RetExpr)) + return false; + for (auto *C = Top; C; C = C->getParent()) + C->emitDestructor(); + if (!this->emitRet(*T, RS)) + return false; + return true; + } + } + return this->bail(RS); + } else { + for (auto *C = Top; C; C = C->getParent()) + C->emitDestructor(); + if (!this->emitRetVoid(RS)) + return false; + return true; + } +} + +template +bool ByteCodeGen::visitIfStmt(const IfStmt *IS) { + BlockScope IfScope(this); + if (auto *CondInit = IS->getInit()) + if (!visit(IS->getInit())) + return false; + + if (auto *CondDecl = IS->getConditionVariableDeclStmt()) + if (!visitDeclStmt(CondDecl)) + return false; + + if (!this->Visit(IS->getCond())) + return false; + + if (auto *Else = IS->getElse()) { + auto LabelElse = this->getLabel(); + auto LabelEnd = this->getLabel(); + if (!this->jumpFalse(LabelElse)) + return false; + if (!visit(IS->getThen())) + return false; + if (!this->jump(LabelEnd)) + return false; + this->emitLabel(LabelElse); + if (!visit(Else)) + return false; + this->emitLabel(LabelEnd); + } else { + auto LabelEnd = this->getLabel(); + if (!this->jumpFalse(LabelEnd)) + return false; + if (!visit(IS->getThen())) + return false; + this->emitLabel(LabelEnd); + } + + return true; +} + +template +bool ByteCodeGen::VisitDeclRefExpr(const DeclRefExpr *DE) { + if (auto *PD = dyn_cast(DE->getDecl())) { + auto It = this->Params.find(PD); + if (It == this->Params.end()) { + return this->emitUndef(DE); + } else { + QualType Ty = PD->getType(); + if (Ty->isReferenceType() || Ctx.isComposite(Ty)) + return this->emitGetParamPtr(It->second, DE); + else + return this->emitGetPtrParam(It->second, DE); + } + } + if (auto *VD = dyn_cast(DE->getDecl())) { + if (!VD->hasLocalStorage()) { + return this->bail(DE); + } + + auto It = Locals.find(VD); + if (It == Locals.end()) { + return this->emitUndef(DE); + } else { + if (VD->getType()->isReferenceType()) + return this->emitGetLocal(PT_Ptr, It->second.Offset, DE); + else + return this->emitGetPtrLocal(It->second.Offset, DE); + } + } + if (auto *ED = dyn_cast(DE->getDecl())) { + QualType Ty = ED->getType(); + if (auto T = Ctx.classify(Ty)) + return this->emitConst(*T, getIntWidth(Ty), ED->getInitVal(), DE); + return this->bail(DE); + } + // TODO: compile other decls. + return this->bail(DE); +} + +template +bool ByteCodeGen::VisitCastExpr(const CastExpr *CE) { + auto *SubExpr = CE->getSubExpr(); + switch (CE->getCastKind()) { + + case CK_LValueToRValue: { + return dereference( + CE->getSubExpr(), AccessKind::Read, + [](PrimType) { + // Value loaded - nothing to do here. + return true; + }, + [this, CE](PrimType T) { + // Pointer on stack - dereference it. + return this->emitLoadPop(T, CE); + }); + } + + case CK_NoOp: { + return this->Visit(SubExpr); + } + + default: { + // TODO: implement other casts. + return this->bail(CE); + } + } +} + +template +bool ByteCodeGen::VisitIntegerLiteral(const IntegerLiteral *LE) { + auto Val = LE->getValue(); + + QualType LitTy = LE->getType(); + if (auto T = Ctx.classify(LitTy)) + return emitConst(*T, getIntWidth(LitTy), LE->getValue(), LE); + return this->bail(LE); +} + +template +bool ByteCodeGen::VisitParenExpr(const ParenExpr *PE) { + return this->Visit(PE->getSubExpr()); +} + +template +bool ByteCodeGen::VisitBinaryOperator(const BinaryOperator *BO) { + // Typecheck the args. + auto *LHS = BO->getLHS(); + auto TypeLHS = Ctx.classify(LHS->getType()); + if (!TypeLHS) { + return this->bail(BO); + } + auto *RHS = BO->getRHS(); + auto TypeRHS = Ctx.classify(RHS->getType()); + if (!TypeRHS) { + return this->bail(BO); + } + + if (auto T = Ctx.classify(BO->getType())) { + switch (BO->getOpcode()) { + case BO_LAnd: { + if (!this->Visit(LHS)) + return false; + auto Short = this->getLabel(); + if (!this->emitDup(*TypeLHS, BO)) + return false; + if (!this->jumpFalse(Short)) + return false; + if (!this->emitPop(*TypeLHS, BO)) + return false; + if (!this->Visit(RHS)) + return false; + this->emitLabel(Short); + return true; + } + case BO_LOr: { + if (!this->Visit(LHS)) + return false; + auto Short = this->getLabel(); + if (!this->emitDup(*TypeLHS, BO)) + return false; + if (!this->jumpTrue(Short)) + return false; + if (!this->emitPop(*TypeLHS, BO)) + return false; + if (!this->Visit(RHS)) + return false; + this->emitLabel(Short); + return true; + } + + case BO_Comma: { + if (!discard(LHS)) + return false; + if (!this->Visit(RHS)) + return false; + return true; + } + + default: + break; + } + + if (!this->Visit(LHS)) + return false; + if (!this->Visit(RHS)) + return false; + + switch (BO->getOpcode()) { + case BO_EQ: + return this->emitEQ(*TypeLHS, BO); + case BO_NE: + return this->emitNE(*TypeLHS, BO); + case BO_LT: + return this->emitLT(*TypeLHS, BO); + case BO_LE: + return this->emitLE(*TypeLHS, BO); + case BO_GT: + return this->emitGT(*TypeLHS, BO); + case BO_GE: + return this->emitGE(*TypeLHS, BO); + case BO_Rem: + return this->emitRem(*T, BO); + case BO_Div: + return this->emitDiv(*T, BO); + case BO_Sub: + return this->emitSub(*T, BO); + case BO_Add: + return this->emitAdd(*T, BO); + case BO_Mul: + return this->emitMul(*T, BO); + default: + return this->bail(BO); + } + } + + return this->bail(BO); +} + +template bool ByteCodeGen::discard(const Expr *DE) { + switch (DE->getStmtClass()) { + case Stmt::BinaryOperatorClass: + return discardBinaryOperator(static_cast(DE)); + default: + if (!this->Visit(DE)) + return false; + if (auto T = Ctx.classify(DE)) + return this->emitPop(*T, DE); + break; + } + + return this->bail(DE); +} + +template +bool ByteCodeGen::discardBinaryOperator(const BinaryOperator *BO) { + // Typecheck the args. + auto *LHS = BO->getLHS(); + auto TypeLHS = Ctx.classify(LHS->getType()); + if (!TypeLHS) { + return this->bail(BO); + } + auto *RHS = BO->getRHS(); + auto TypeRHS = Ctx.classify(RHS->getType()); + if (!TypeRHS) { + return this->bail(BO); + } + + // Peephole optimisations. + if (auto T = Ctx.classify(BO->getType())) { + // Handle operations with mixed types. + switch (BO->getOpcode()) { + case BO_Comma: + if (!discard(LHS)) + return false; + if (!discard(RHS)) + return false; + return true; + default: + break; + } + + if (!this->Visit(BO)) + return false; + return this->emitPop(*T, BO); + } else { + return this->bail(BO); + } +} + +template +bool ByteCodeGen::dereference( + const Expr *LV, AccessKind AK, llvm::function_ref Direct, + llvm::function_ref Indirect) { + auto T = Ctx.classify(LV->getType()); + if (!T) + return this->bail(LV); + + if (auto *DE = dyn_cast(LV)) { + if (!DE->getDecl()->getType()->isReferenceType()) { + if (auto *PD = dyn_cast(DE->getDecl())) { + auto It = this->Params.find(PD); + if (It != this->Params.end()) { + unsigned Idx = It->second; + switch (AK) { + case AccessKind::Read: + if (!this->emitGetParam(*T, Idx, LV)) + return false; + break; + case AccessKind::Write: + if (!Direct(*T)) + return false; + if (!this->emitSetParam(*T, Idx, LV)) + return false; + if (!this->emitGetPtrParam(Idx, LV)) + return false; + break; + case AccessKind::WriteVoid: + if (!Direct(*T)) + return false; + if (!this->emitSetParam(*T, Idx, LV)) + return false; + break; + case AccessKind::ReadWrite: + if (!this->emitGetParam(*T, Idx, LV)) + return false; + if (!Direct(*T)) + return false; + if (!this->emitSetParam(*T, Idx, LV)) + return false; + if (!this->emitGetPtrParam(Idx, LV)) + return false; + break; + case AccessKind::ReadWriteVoid: + if (!this->emitGetParam(*T, Idx, LV)) + return false; + if (!Direct(*T)) + return false; + if (!this->emitSetParam(*T, Idx, LV)) + return false; + break; + } + return true; + } else { + // If the param is a pointer, we can dereference a dummy value. + if (PD->getType()->hasPointerRepresentation()) { + if (AK == AccessKind::Read) { + if (!this->emitUndef(LV)) + return false; + return Direct(*T); + } + } + } + } + if (auto *VD = dyn_cast(DE->getDecl())) { + auto It = Locals.find(VD); + if (It != Locals.end()) { + const auto &L = It->second; + switch (AK) { + case AccessKind::Read: { + if (!this->emitGetLocal(*T, L.Offset, LV)) + return false; + break; + } + case AccessKind::Write: { + if (!Direct(*T)) + return false; + if (!this->emitSetLocal(*T, L.Offset, LV)) + return false; + if (!this->emitGetPtrLocal(L.Offset, LV)) + return false; + break; + } + case AccessKind::WriteVoid: { + if (!Direct(*T)) + return false; + if (!this->emitSetLocal(*T, L.Offset, LV)) + return false; + break; + } + case AccessKind::ReadWrite: { + if (!this->emitGetLocal(*T, L.Offset, LV)) + return false; + if (!Direct(*T)) + return false; + if (!this->emitSetLocal(*T, L.Offset, LV)) + return false; + if (!this->emitGetPtrLocal(L.Offset, LV)) + return false; + break; + } + case AccessKind::ReadWriteVoid: { + if (!this->emitGetLocal(*T, L.Offset, LV)) + return false; + if (!Direct(*T)) + return false; + if (!this->emitSetLocal(*T, L.Offset, LV)) + return false; + break; + } + } + return true; + } else { + // If the declaration is a constant value, emit it here even + // though the declaration was not evaluated in the current scope. + // The access mode can only be read in this case. + if (VD->hasLocalStorage()) { + auto VT = VD->getType(); + if (VT.isConstQualified() && VT->isFundamentalType()) { + if (AK == AccessKind::Read) { + if (!this->Visit(VD->getInit())) + return false; + return Direct(*T); + } + } + } + } + } + } + } + + if (!this->Visit(LV)) + return false; + return Indirect(*T); +} + +template +bool ByteCodeGen::visitVarDecl(const VarDecl *VD) { + auto DT = VD->getType(); + + if (!VD->hasLocalStorage()) { + // No code generation required. + return true; + } + + // Integers, pointers, primitives. + if (auto T = Ctx.classify(DT)) { + auto Off = allocateLocalPrimitive(VD, *T, !DT.isConstQualified()); + // Compile the initialiser in its own scope. + { + ExprScope Scope(this); + if (!this->Visit(VD->getInit())) + return false; + } + // Set the value. + return this->emitSetLocal(*T, Off, VD); + } else { + return this->bail(VD); + } +} + +template +bool ByteCodeGen::emitConst(PrimType T, unsigned NumBits, + const APInt &Value, const Expr *E) { + switch (T) { + case PT_Sint8: + return this->emitConstSint8(Value.getSExtValue(), E); + case PT_Uint8: + return this->emitConstUint8(Value.getZExtValue(), E); + case PT_Sint16: + return this->emitConstSint16(Value.getSExtValue(), E); + case PT_Uint16: + return this->emitConstUint16(Value.getZExtValue(), E); + case PT_Sint32: + return this->emitConstSint32(Value.getSExtValue(), E); + case PT_Uint32: + return this->emitConstUint32(Value.getZExtValue(), E); + case PT_Sint64: + return this->emitConstSint64(Value.getSExtValue(), E); + case PT_Uint64: + return this->emitConstUint64(Value.getZExtValue(), E); + case PT_Bool: + return this->emitConstBool(Value.getBoolValue(), E); + case PT_Ptr: + llvm_unreachable("Invalid integral type"); + break; + } +} + +template +unsigned +ByteCodeGen::allocateLocalPrimitive(DeclTy &&Decl, PrimType Ty, + bool IsMutable, bool IsExtended) { + Descriptor *D = P.createDescriptor(std::move(Decl), Ty, IsMutable, + Decl.is()); + Scope::Local Local = this->createLocal(D); + if (auto *VD = Decl.dyn_cast()) + Locals.insert({VD, Local}); + Top->add(Local, IsExtended); + return Local.Offset; +} + +template +bool ByteCodeGen::visitArgument(const Expr *E) { + // Primitive or pointer argument - leave it on the stack. + if (auto T = Ctx.classify(E)) + return this->Visit(E); + + // Composite argument - copy construct and push pointer. + return this->bail(E); +} + +template bool ByteCodeGen::compile(const Expr *Exp) { + ExprScope RootScope(this); + if (!this->ConstStmtVisitor, bool>::Visit(Exp)) + return false; + + if (auto T = Ctx.classify(Exp)) + return this->emitRet(*T, Exp); + + return false; +} + +template +bool ByteCodeGen::compile(const FunctionDecl *F) { + // Set up fields and context if a constructor. + if (auto *MD = dyn_cast(F)) { + return this->bail(MD); + } + + if (auto *Body = F->getBody()) + if (!visit(Body)) + return false; + + // Emit a guard return to protect against a code path missing one. + if (F->getReturnType()->isVoidType()) + return this->emitRetVoid({}); + else + return this->emitNoRet({}); +} + +template bool ByteCodeGen::compile(const VarDecl *VD) { + auto VT = VD->getType(); + auto Init = VD->getInit(); + + DeclScope LocalScope(this); + + if (auto T = Ctx.classify(VT)) { + // Primitive declarations - compute the value and set a global. + if (!this->ConstStmtVisitor, bool>::Visit(Init)) + return false; + if (VD->hasLocalStorage()) + return this->emitPop(*T, VD); + return this->bail(VD); + } else { + // Composite declarations - allocate storage and initialize it. + return this->bail(VD); + } +} + +namespace clang { +namespace interp { + +template class ByteCodeGen; +template class ByteCodeGen; + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/ByteCodeGenError.h b/clang/lib/AST/Interp/ByteCodeGenError.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeGenError.h @@ -0,0 +1,46 @@ +//===--- ByteCodeGenError.h - Byte code generation error ----------*- C -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_BYTECODEGENERROR_H +#define LLVM_CLANG_AST_INTERP_BYTECODEGENERROR_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/Basic/SourceLocation.h" +#include "llvm/Support/Error.h" + +namespace clang { +namespace interp { + +/// Error thrown by the compiler. +struct ByteCodeGenError : public llvm::ErrorInfo { +public: + ByteCodeGenError(SourceLocation Loc) : Loc(Loc) {} + ByteCodeGenError(const Stmt *S) : ByteCodeGenError(S->getBeginLoc()) {} + ByteCodeGenError(const Decl *D) : ByteCodeGenError(D->getBeginLoc()) {} + + void log(raw_ostream &OS) const override { OS << "unimplemented feature"; } + + const SourceLocation &getLoc() const { return Loc; } + + static char ID; + +private: + // Start of the item where the error occurred. + SourceLocation Loc; + + // Users are not expected to use error_code. + std::error_code convertToErrorCode() const override { + return llvm::inconvertibleErrorCode(); + } +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/ByteCodeGenError.cpp b/clang/lib/AST/Interp/ByteCodeGenError.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeGenError.cpp @@ -0,0 +1,14 @@ +//===--- ByteCodeGenError.h - Byte code generation error --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "ByteCodeGenError.h" + +using namespace clang; +using namespace clang::interp; + +char ByteCodeGenError::ID; diff --git a/clang/lib/AST/Interp/CMakeLists.txt b/clang/lib/AST/Interp/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/CMakeLists.txt @@ -0,0 +1,31 @@ +set(LLVM_LINK_COMPONENTS + ) + +clang_tablegen(Opcodes.inc + -gen-clang-opcodes + SOURCE Opcodes.td + TARGET Opcodes) + +add_clang_library(clangInterp + ByteCodeGen.cpp + ByteCodeGenError.cpp + Context.cpp + Descriptor.cpp + Disasm.cpp + EvalEmitter.cpp + Frame.cpp + Function.cpp + Interp.cpp + InterpFrame.cpp + InterpStack.cpp + InterpState.cpp + LinkEmitter.cpp + Pointer.cpp + Program.cpp + Source.cpp + State.cpp + Type.cpp + + DEPENDS + Opcodes + ) diff --git a/clang/lib/AST/Interp/Context.h b/clang/lib/AST/Interp/Context.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Context.h @@ -0,0 +1,105 @@ +//===--- Context.h - Context for the constexpr VM ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the constexpr execution context. +// +// The execution context manages cached bytecode and the global context. +// It invokes the compiler and interpreter, propagating errors. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_CONTEXT_H +#define LLVM_CLANG_AST_INTERP_CONTEXT_H + +#include "Context.h" +#include "InterpStack.h" +#include "clang/AST/APValue.h" +#include "llvm/ADT/PointerIntPair.h" + +namespace clang { +class ASTContext; +class LangOptions; +class Stmt; +class FunctionDecl; +class VarDecl; + +namespace interp { +class Function; +class Program; +class State; +enum PrimType : unsigned; + +/// Wrapper around interpreter termination results. +enum class InterpResult { + /// Interpreter successfully computed a value. + Success, + /// Interpreter encountered an error and quit. + Fail, + /// Interpreter encountered an unimplemented feature, AST fallback. + Bail, +}; + +/// Holds all information required to evaluate constexpr code in a module. +class Context { +public: + /// Initialises the constexpr VM. + Context(ASTContext &Ctx); + + /// Cleans up the constexpr VM. + ~Context(); + + /// Compiles and runs a function with a given set of arguments. + InterpResult handleFunctionCall(State &Parent, const FunctionDecl *FnDecl, + llvm::ArrayRef Args, + APValue &Result); + + /// Checks if a function is a potential constant expression. + InterpResult isPotentialConstantExpr(State &Parent, + const FunctionDecl *FnDecl); + + /// Evaluates a toplevel expression as an rvalue. + InterpResult evaluateAsRValue(State &Parent, const Expr *E, APValue &Result); + + /// Evaluates a toplevel initializer. + InterpResult evaluateAsInitializer(State &Parent, const VarDecl *VD, + APValue &Result); + + /// Returns the AST context. + ASTContext &getASTContext() const { return Ctx; } + /// Returns the language options. + const LangOptions &getLangOpts() const; + + /// Classifies an expression. + llvm::Optional classify(QualType T); + /// Classifies a type. + llvm::Optional classify(const Expr *E); + /// Checks if a type cannot be mapped to a VM type. + bool isComposite(QualType T) const; + +private: + /// Runs a function. + InterpResult Run(State &Parent, Function *Func, APValue &Result); + + /// Checks a result fromt the interpreter. + InterpResult Check(State &Parent, llvm::Expected &&R); + +private: + /// Current compilation context. + ASTContext &Ctx; + /// Flag to indicate if the use of the interpreter is mandatory. + bool ForceInterp; + /// Interpreter stack, shared across invocations. + InterpStack Stk; + /// Constexpr program. + std::unique_ptr P; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Context.cpp b/clang/lib/AST/Interp/Context.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Context.cpp @@ -0,0 +1,213 @@ +//===--- Context.cpp - Context for the constexpr VM -------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Context.h" +#include "ByteCodeGen.h" +#include "EvalEmitter.h" +#include "Interp.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "LinkEmitter.h" +#include "Program.h" +#include "Type.h" +#include "clang/AST/Expr.h" + +using namespace clang; +using namespace clang::interp; + +Context::Context(ASTContext &Ctx) + : Ctx(Ctx), ForceInterp(getLangOpts().ForceClangInterp), + P(new Program(*this)) {} + +Context::~Context() {} + +InterpResult Context::handleFunctionCall(State &Parent, + const FunctionDecl *FnDecl, + llvm::ArrayRef Args, + APValue &Result) { + assert(Stk.size() == 0 && "Empty stack expected on execution start"); + + // Compile the function. + Function *Func = P->getFunction(FnDecl); + if (!Func) { + if (auto R = + ByteCodeGen(*this, Parent, *P).compileFunc(FnDecl)) { + Func = *R; + } else if (ForceInterp) { + handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) { + Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed); + }); + return InterpResult::Fail; + } else { + consumeError(R.takeError()); + return InterpResult::Bail; + } + } + + // Convert the arguments and store them on the stack. + if (!Parent.checkingPotentialConstantExpression()) { + assert(Args.size() == FnDecl->getNumParams() && "Missing arguments"); + + for (unsigned I = 0, N = FnDecl->getNumParams(); I < N; ++I) { + auto *ParamDecl = FnDecl->getParamDecl(I); + auto &Value = Args[I]; + + switch (*classify(ParamDecl->getType())) { + case PT_Sint8: + Stk.push::T>(Value.getInt()); + break; + case PT_Uint8: + Stk.push::T>(Value.getInt()); + break; + case PT_Sint16: + Stk.push::T>(Value.getInt()); + break; + case PT_Uint16: + Stk.push::T>(Value.getInt()); + break; + case PT_Sint32: + Stk.push::T>(Value.getInt()); + break; + case PT_Uint32: + Stk.push::T>(Value.getInt()); + break; + case PT_Sint64: + Stk.push::T>(Value.getInt()); + break; + case PT_Uint64: + Stk.push::T>(Value.getInt()); + break; + case PT_Bool: + Stk.push::T>(Value.getInt()); + break; + case PT_Ptr: + if (ForceInterp) { + const auto &Loc = Func->getLoc(); + Parent.FFDiag(Loc, diag::err_experimental_clang_interp_failed); + return InterpResult::Fail; + } else { + return InterpResult::Bail; + } + } + } + } + + return Run(Parent, Func, Result); +} + +InterpResult Context::isPotentialConstantExpr(State &Parent, + const FunctionDecl *FD) { + Function *Func = P->getFunction(FD); + if (!Func) { + if (auto R = ByteCodeGen(*this, Parent, *P).compileFunc(FD)) { + Func = *R; + } else if (ForceInterp) { + handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) { + Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed); + }); + return InterpResult::Fail; + } else { + consumeError(R.takeError()); + return InterpResult::Bail; + } + } + + APValue Dummy; + return Run(Parent, Func, Dummy); +} + +InterpResult Context::evaluateAsRValue(State &Parent, const Expr *E, + APValue &Result) { + ByteCodeGen C(*this, Parent, *P, Stk, Result); + return Check(Parent, C.interpretExpr(E)); +} + +InterpResult Context::evaluateAsInitializer(State &Parent, const VarDecl *VD, + APValue &Result) { + ByteCodeGen C(*this, Parent, *P, Stk, Result); + return Check(Parent, C.interpretDecl(VD)); +} + +const LangOptions &Context::getLangOpts() const { return Ctx.getLangOpts(); } + +llvm::Optional Context::classify(QualType T) { + if (T->isBooleanType()) { + return PT_Bool; + } + + if (T->isSignedIntegerOrEnumerationType()) { + switch (Ctx.getIntWidth(T)) { + case 64: + return PT_Sint64; + case 32: + return PT_Sint32; + case 16: + return PT_Sint16; + case 8: + return PT_Sint8; + default: + return {}; + } + } + + if (T->isUnsignedIntegerOrEnumerationType()) { + switch (Ctx.getIntWidth(T)) { + case 64: + return PT_Uint64; + case 32: + return PT_Uint32; + case 16: + return PT_Uint16; + case 8: + return PT_Uint8; + default: + return {}; + } + } + + if (T->isNullPtrType() || T->isReferenceType() || T->isPointerType()) + return PT_Ptr; + + return {}; +} + +llvm::Optional Context::classify(const Expr *E) { + if (E->isGLValue()) + return PT_Ptr; + return classify(E->getType()); +} + +bool Context::isComposite(QualType T) const { + return !T->isFundamentalType() && !T->isEnumeralType() && + !T->hasPointerRepresentation(); +} + +InterpResult Context::Run(State &Parent, Function *Func, APValue &Result) { + InterpState State(Parent, *P, Stk, *this); + State.Current = new InterpFrame(State, Func, nullptr, {}, {}); + if (Interpret(State, Result)) { + return InterpResult::Success; + } else { + Stk.clear(); + return InterpResult::Fail; + } +} + +InterpResult Context::Check(State &Parent, llvm::Expected &&R) { + if (R) { + return *R ? InterpResult::Success : InterpResult::Fail; + } else if (ForceInterp) { + handleAllErrors(R.takeError(), [&Parent](ByteCodeGenError &Err) { + Parent.FFDiag(Err.getLoc(), diag::err_experimental_clang_interp_failed); + }); + return InterpResult::Fail; + } else { + consumeError(R.takeError()); + return InterpResult::Bail; + } +} diff --git a/clang/lib/AST/Interp/Descriptor.h b/clang/lib/AST/Interp/Descriptor.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Descriptor.h @@ -0,0 +1,90 @@ +//===--- Descriptor.h - Types for the constexpr VM --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines descriptors which characterise allocations. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_DESCRIPTOR_H +#define LLVM_CLANG_AST_INTERP_DESCRIPTOR_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" + +namespace clang { +namespace interp { +class Block; +class Record; +struct Descriptor; +enum PrimType : unsigned; + +using DeclTy = llvm::PointerUnion; + +/// Handlers managing object lifetimes. +using BlockCtorFn = void (*)(Block *B, char *, bool, Descriptor *); +using BlockDtorFn = void (*)(Block *B, char *, Descriptor *); +using BlockMoveFn = void (*)(Block *B, char *, char *, Descriptor *); + +/// Object size as used by the interpreter. +using InterpSize = unsigned; + +/// Describes a memory block created by an allocation site. +struct Descriptor { + /// Original declaration, used to emit the error message. + const DeclTy Source; + /// Size of an element. + const InterpSize ElemSize; + /// Size of the allocation, in bytes. + const InterpSize Size; + /// Pointer to the record, if block contains records. + Record *const ElemRecord = nullptr; + /// Descriptor of the array element. + Descriptor *const ElemDesc = nullptr; + /// Flag indicating if the block is mutable. + const bool IsMutable = false; + /// Flag indicating if the block is a temporary. + const bool IsTemporary = false; + /// Flag indicating if the block is an array. + const bool IsArray = false; + + /// Invoked whenever a block is created. The constructor method fills in the + /// inline descriptors of all fields and array elements. It also initializes + /// all the fields which contain non-trivial types. + const BlockCtorFn CtorFn = nullptr; + /// Invoked when a block is destroyed. Invokes the destructors of all + /// non-trivial nested fields of arrays and records. + const BlockDtorFn DtorFn = nullptr; + /// Invoked when a block with pointers referencing it goes out of scoped. Such + /// blocks are persisted: the move function copies all inline descriptors and + /// non-trivial fields, as existing pointers might need to reference those + /// descriptors. Data is not copied since it cannot be legally read. + const BlockMoveFn MoveFn = nullptr; + + QualType getType() const; + SourceLocation getLocation() const; + + /// Allocates a descriptor for a primitive. + Descriptor(const DeclTy &D, PrimType Type, bool IsMutable, bool IsTemporary); +}; + +/// Inline descriptor embedded in structures and arrays. +struct InlineDescriptor { + /// Offset from the start of the record or array. + unsigned Offset; + /// Flag indicating whether storage is mutable. + bool IsMutable; + /// Flag indicating whether a record field was initialised. + bool IsInitialized; + /// Pointer to the array element or field descriptor. + Descriptor *Desc; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Descriptor.cpp b/clang/lib/AST/Interp/Descriptor.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Descriptor.cpp @@ -0,0 +1,74 @@ +//===--- Descriptor.cpp - Types for the constexpr VM ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Descriptor.h" +#include "Pointer.h" +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +template +static void ctorTy(Block *, char *Ptr, bool, Descriptor *) { + new (Ptr) T(); +} + +template +static void dtorTy(Block *, char *Ptr, Descriptor *) { + reinterpret_cast(Ptr)->~T(); +} + +template +static void moveTy(Block *, char *Src, char *Dst, Descriptor *) { + auto *SrcPtr = reinterpret_cast(Src); + auto *DstPtr = reinterpret_cast(Dst); + new (DstPtr) T(std::move(*SrcPtr)); +} + +static BlockCtorFn getCtorPrim(PrimType Type) { + switch (Type) { + case PT_Ptr: return ctorTy::T>; + default: return nullptr; + } +} + +static BlockDtorFn getDtorPrim(PrimType Type) { + switch (Type) { + case PT_Ptr: return dtorTy::T>; + default: return nullptr; + } +} + +static BlockMoveFn getMovePrim(PrimType Type) { + switch (Type) { + case PT_Ptr: return moveTy::T>; + default: return nullptr; + } +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsMutable, + bool IsTemporary) + : Source(D), ElemSize(primSize(Type)), Size(ElemSize), IsMutable(IsMutable), + IsTemporary(IsTemporary), CtorFn(getCtorPrim(Type)), + DtorFn(getDtorPrim(Type)), MoveFn(getMovePrim(Type)) {} + +QualType Descriptor::getType() const { + if (auto *D = Source.dyn_cast()) + return D->getType(); + if (auto *E = Source.dyn_cast()) + return E->getType(); + llvm_unreachable("Invalid descriptor type"); +} + +SourceLocation Descriptor::getLocation() const { + if (auto *D = Source.dyn_cast()) + return D->getLocation(); + if (auto *E = Source.dyn_cast()) + return E->getExprLoc(); + llvm_unreachable("Invalid descriptor type"); +} diff --git a/clang/lib/AST/Interp/Disasm.cpp b/clang/lib/AST/Interp/Disasm.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Disasm.cpp @@ -0,0 +1,65 @@ +//===--- Disasm.cpp - Disassembler for bytecode functions -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Dump method for Function which disassembles the bytecode. +// +//===----------------------------------------------------------------------===// + +#include "Function.h" +#include "Opcode.h" +#include "Program.h" +#include "Type.h" +#include "clang/AST/DeclCXX.h" +#include "llvm/Support/Compiler.h" + +using namespace clang; +using namespace clang::interp; + +LLVM_DUMP_METHOD void Function::dump() const { dump(llvm::errs()); } + +LLVM_DUMP_METHOD void Function::dump(llvm::raw_ostream &OS) const { + if (F) { + if (auto *Cons = dyn_cast(F)) { + auto Name = Cons->getParent()->getName(); + OS << Name << "::" << Name << ":\n"; + } else { + OS << F->getName() << ":\n"; + } + } else { + OS << "<>\n"; + } + + auto PrintName = [&OS](const char *Name) { + OS << Name; + for (long I = 0, N = strlen(Name); I < 30 - N; ++I) { + OS << ' '; + } + }; + + for (auto Start = getCodeBegin(), PC = Start; PC != getCodeEnd();) { + size_t Addr = PC - Start; + auto Op = PC.read(); + OS << llvm::format("%8d", Addr) << " "; + switch (Op) { +#define GET_DISASM +#include "Opcodes.inc" +#undef GET_DISASM + } + } +} + +LLVM_DUMP_METHOD void Program::dump() const { dump(llvm::errs()); } + +LLVM_DUMP_METHOD void Program::dump(llvm::raw_ostream &OS) const { + for (auto &Func : Funcs) { + Func.second->dump(); + } + for (auto &Anon : AnonFuncs) { + Anon->dump(); + } +} diff --git a/clang/lib/AST/Interp/EvalEmitter.h b/clang/lib/AST/Interp/EvalEmitter.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/EvalEmitter.h @@ -0,0 +1,125 @@ +//===--- EvalEmitter.h - Instruction emitter for the VM ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the instruction emitters. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_EVALEMITTER_H +#define LLVM_CLANG_AST_INTERP_EVALEMITTER_H + +#include "ByteCodeGenError.h" +#include "Context.h" +#include "InterpStack.h" +#include "InterpState.h" +#include "Program.h" +#include "Source.h" +#include "Type.h" +#include "llvm/Support/Error.h" + +namespace clang { +class FunctionDecl; +namespace interp { +class Context; +class Function; +class InterpState; +class Program; +class SourceInfo; +enum Opcode : uint32_t; + +/// An emitter which evaluates opcodes as they are emitted. +class EvalEmitter : public SourceMapper { +public: + using LabelTy = uint32_t; + using AddrTy = uintptr_t; + using Local = Scope::Local; + + llvm::Expected interpretExpr(const Expr *E); + llvm::Expected interpretDecl(const VarDecl *VD); + +protected: + EvalEmitter(Context &Ctx, State &Parent, Program &P, InterpStack &Stk, + APValue &Result); + + virtual ~EvalEmitter() {} + + /// Define a label. + void emitLabel(LabelTy Label); + /// Create a label. + LabelTy getLabel(); + + /// Methods implemented by the compiler. + virtual bool compile(const FunctionDecl *E) = 0; + virtual bool compile(const Expr *E) = 0; + virtual bool compile(const VarDecl *VD) = 0; + + bool bail(const Stmt *S) { return bail(S->getBeginLoc()); } + bool bail(const Decl *D) { return bail(D->getBeginLoc()); } + bool bail(const SourceLocation &Loc); + + /// Emits jumps. + bool jumpTrue(const LabelTy &Label); + bool jumpFalse(const LabelTy &Label); + bool jump(const LabelTy &Label); + bool fallthrough(const LabelTy &Label); + + /// Callback for registering a local. + Local createLocal(Descriptor *D); + + /// Returns the source location of the current opcode. + SourceInfo getSource(Function *F, CodePtr PC) const override { + return F ? F->getSource(PC) : CurrentSource; + } + + /// Parameter indices. + llvm::DenseMap Params; + /// Local descriptors. + llvm::SmallVector, 2> Descriptors; + +private: + /// Current compilation context. + Context &Ctx; + /// Current program. + Program &P; + /// Callee evaluation state. + InterpState S; + /// Location to write the result to. + APValue &Result; + + /// Temporaries which require storage. + llvm::DenseMap> Locals; + + // The emitter always tracks the current instruction and sets OpPC to a token + // value which is mapped to the location of the opcode being evaluated. + CodePtr OpPC; + /// Location of a failure. + llvm::Optional BailLocation; + /// Location of the current instruction. + SourceInfo CurrentSource; + + /// Next label ID to generate - first label is 1. + LabelTy NextLabel = 1; + /// Label being executed - 0 is the entry label. + LabelTy CurrentLabel = 0; + /// Active block which should be executed. + LabelTy ActiveLabel = 0; + + /// Since expressions can only jump forward, predicated execution is + /// used to deal with if-else statements. + bool isActive() { return CurrentLabel == ActiveLabel; } + +protected: +#define GET_EVAL_PROTO +#include "Opcodes.inc" +#undef GET_EVAL_PROTO +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/EvalEmitter.cpp b/clang/lib/AST/Interp/EvalEmitter.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/EvalEmitter.cpp @@ -0,0 +1,172 @@ +//===--- EvalEmitter.cpp - Instruction emitter for the VM -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "EvalEmitter.h" +#include "Context.h" +#include "Interp.h" +#include "Opcode.h" +#include "Program.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +using Error = llvm::Error; + +EvalEmitter::EvalEmitter(Context &Ctx, State &Parent, Program &P, + InterpStack &Stk, APValue &Result) + : Ctx(Ctx), P(P), S(Parent, P, Stk, Ctx, this), Result(Result) { + // Create a dummy frame for the interpreter which does not have locals. + S.Current = new InterpFrame(S, nullptr, nullptr, {}, {}); +} + +llvm::Expected EvalEmitter::interpretExpr(const Expr *E) { + assert(S.Stk.size() == 0 && "empty stack expected by evaluator"); + + bool Success = this->compile(E); + S.Stk.clear(); + if (!Success && BailLocation) + return llvm::make_error(*BailLocation); + + return Success; +} + +llvm::Expected EvalEmitter::interpretDecl(const VarDecl *VD) { + assert(S.Stk.size() == 0 && "empty stack expected by evaluator"); + + bool Success = this->compile(VD); + S.Stk.clear(); + if (!Success && BailLocation) + return llvm::make_error(*BailLocation); + + return Success; +} + +void EvalEmitter::emitLabel(LabelTy Label) { + CurrentLabel = Label; +} + +EvalEmitter::LabelTy EvalEmitter::getLabel() { return NextLabel++; } + +Scope::Local EvalEmitter::createLocal(Descriptor *D) { + // Allocate memory for a local. + auto Memory = llvm::make_unique(sizeof(Block) + D->Size); + auto *B = new (Memory.get()) Block(D, /*isStatic=*/false); + + if (D->CtorFn) + D->CtorFn(B, B->data(), D->IsMutable, D); + + // Register the local. + unsigned Off = Locals.size(); + Locals.insert({Off, std::move(Memory)}); + return {Off, D}; +} + +bool EvalEmitter::bail(const SourceLocation &Loc) { + if (!BailLocation) + BailLocation = Loc; + return false; +} + +bool EvalEmitter::jumpTrue(const LabelTy &Label) { + if (isActive()) { + if (S.Stk.pop()) + ActiveLabel = Label; + } + return true; +} + +bool EvalEmitter::jumpFalse(const LabelTy &Label) { + if (isActive()) { + if (!S.Stk.pop()) + ActiveLabel = Label; + } + return true; +} + +bool EvalEmitter::jump(const LabelTy &Label) { + if (isActive()) + CurrentLabel = ActiveLabel = Label; + return true; +} + +bool EvalEmitter::fallthrough(const LabelTy &Label) { + if (isActive()) + ActiveLabel = Label; + return true; +} + +template bool EvalEmitter::emitRet(const SourceInfo &Info) { + if (!isActive()) { + return true; + } + using T = typename PrimConv::T; + return ReturnValue(S.Stk.pop(), Result); +} + +bool EvalEmitter::emitRetVoid(const SourceInfo &Info) { return true; } + +bool EvalEmitter::emitGetPtrLocal(const uint32_t &I, const SourceInfo &Info) { + if (!isActive()) + return true; + + auto It = Locals.find(I); + assert(It != Locals.end() && "Missing local variable"); + S.Stk.push(reinterpret_cast(It->second.get())); + return true; +} + +template +bool EvalEmitter::emitGetLocal(const uint32_t &I, const SourceInfo &Info) { + if (!isActive()) + return true; + + using T = typename PrimConv::T; + + auto It = Locals.find(I); + assert(It != Locals.end() && "Missing local variable"); + auto *B = reinterpret_cast(It->second.get()); + S.Stk.push(*reinterpret_cast(B + 1)); + return true; +} + +template +bool EvalEmitter::emitSetLocal(const uint32_t &I, const SourceInfo &Info) { + if (!isActive()) + return true; + + using T = typename PrimConv::T; + + auto It = Locals.find(I); + assert(It != Locals.end() && "Missing local variable"); + auto *B = reinterpret_cast(It->second.get()); + *reinterpret_cast(B + 1) = S.Stk.pop(); + return true; +} + +bool EvalEmitter::emitDestroy(const uint32_t &I, const SourceInfo &Info) { + if (!isActive()) + return true; + + for (auto &Local : Descriptors[I]) { + auto It = Locals.find(Local.Offset); + assert(It != Locals.end() && "Missing local variable"); + S.deallocate(reinterpret_cast(It->second.get())); + } + + return true; +} + +//===----------------------------------------------------------------------===// +// Opcode evaluators +//===----------------------------------------------------------------------===// + +#define GET_EVAL_IMPL +#include "Opcodes.inc" +#undef GET_EVAL_IMPL diff --git a/clang/lib/AST/Interp/Frame.h b/clang/lib/AST/Interp/Frame.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Frame.h @@ -0,0 +1,45 @@ +//===--- Frame.h - Call frame for the VM and AST Walker ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the base class of interpreter and evaluator stack frames. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_FRAME_H +#define LLVM_CLANG_AST_INTERP_FRAME_H + +#include "clang/Basic/SourceLocation.h" +#include "llvm/Support/raw_ostream.h" + +namespace clang { +class FunctionDecl; + +namespace interp { + +/// Base class for stack frames, shared between VM and walker. +class Frame { +public: + virtual ~Frame(); + + /// Generates a human-readable description of the call site. + virtual void describe(llvm::raw_ostream &OS) = 0; + + /// Returns a pointer to the caller frame. + virtual Frame *getCaller() const = 0; + + /// Returns the location of the call site. + virtual SourceLocation getCallLocation() const = 0; + + /// Returns the called function's declaration. + virtual const FunctionDecl *getCallee() const = 0; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Frame.cpp b/clang/lib/AST/Interp/Frame.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Frame.cpp @@ -0,0 +1,14 @@ +//===--- Frame.cpp - Call frame for the VM and AST Walker -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Frame.h" + +using namespace clang; +using namespace clang::interp; + +Frame::~Frame() {} diff --git a/clang/lib/AST/Interp/Function.h b/clang/lib/AST/Interp/Function.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Function.h @@ -0,0 +1,139 @@ +//===--- Function.h - Bytecode function for the VM --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the Function class which holds all bytecode function-specific data. +// +// The scope class which describes local variables is also defined here. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_FUNCTION_H +#define LLVM_CLANG_AST_INTERP_FUNCTION_H + +#include "Pointer.h" +#include "Source.h" +#include "clang/AST/Decl.h" +#include "llvm/Support/raw_ostream.h" + +namespace clang { +namespace interp { +class Program; +enum PrimType : uint32_t; + +/// Describes a scope block. +/// +/// The block gathers all the descriptors of the locals defined in this block. +class Scope { +public: + /// Information about a local's storage. + struct Local { + /// Offset of the local in frame. + unsigned Offset; + /// Descriptor of the local. + Descriptor *Desc; + }; + + using LocalVectorTy = llvm::SmallVector; + + Scope(LocalVectorTy &&Descriptors) : Descriptors(std::move(Descriptors)) {} + + llvm::iterator_range locals() { + return llvm::make_range(Descriptors.begin(), Descriptors.end()); + } + +private: + /// Object descriptors in this block. + LocalVectorTy Descriptors; +}; + +/// Bytecode function. +/// +/// Contains links to the bytecode of the function, as well as metadata +/// describing all arguments and stack-local variables. +class Function { +public: + using ParamDescriptor = std::pair; + + /// Returns the size of the function's local stack. + unsigned getFrameSize() const { return FrameSize; } + /// Returns the size of the argument stackx + unsigned getArgSize() const { return ArgSize; } + + /// Returns a pointer to the start of the code. + CodePtr getCodeBegin() const; + /// Returns a pointer to the end of the code. + CodePtr getCodeEnd() const; + + /// Returns the original FunctionDecl. + const FunctionDecl *getDecl() const { return F; } + + /// Returns the lcoation. + SourceLocation getLoc() const { return Loc; } + + /// Returns a parameter descriptor. + ParamDescriptor getParamDescriptor(unsigned Offset) const; + + /// Range over the scope blocks. + llvm::iterator_range::iterator> scopes() { + return llvm::make_range(Scopes.begin(), Scopes.end()); + } + + /// Range over argument types. + using arg_reverse_iterator = SmallVectorImpl::reverse_iterator; + llvm::iterator_range args_reverse() { + return llvm::make_range(ParamTypes.rbegin(), ParamTypes.rend()); + } + + /// Returns a specific scope. + Scope &getScope(unsigned Idx) { return Scopes[Idx]; } + + /// Returns the source information at a given PC. + SourceInfo getSource(CodePtr PC) const; + +private: + /// Construct a function representing an actual function. + Function(Program &P, const FunctionDecl *F, unsigned FrameSize, + unsigned ArgSize, std::vector &&Code, SourceMap &&SrcMap, + llvm::SmallVector &&Scopes, + llvm::SmallVector &&ParamTypes, + llvm::DenseMap &&Params); + +private: + friend class Program; + + /// Program reference. + Program &P; + /// Location of the executed code. + SourceLocation Loc; + /// Declaration this function was compiled from. + const FunctionDecl *F; + /// Local area size: storage + metadata. + unsigned FrameSize; + /// Size of the argument stack. + unsigned ArgSize; + /// Program code. + std::vector Code; + /// Opcode-to-expression mapping. + SourceMap SrcMap; + /// List of block descriptors. + llvm::SmallVector Scopes; + /// List of argument types. + llvm::SmallVector ParamTypes; + /// Map from byte offset to parameter descriptor. + llvm::DenseMap Params; + +public: + /// Dumps the disassembled bytecode to \c llvm::errs(). + void dump() const; + void dump(llvm::raw_ostream &OS) const; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Function.cpp b/clang/lib/AST/Interp/Function.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Function.cpp @@ -0,0 +1,45 @@ +//===--- Function.h - Bytecode function for the VM --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Function.h" +#include "Program.h" +#include "Opcode.h" +#include "clang/AST/Decl.h" + +using namespace clang; +using namespace clang::interp; + +Function::Function(Program &P, const FunctionDecl *F, unsigned FrameSize, + unsigned ArgSize, std::vector &&Code, + SourceMap &&SrcMap, llvm::SmallVector &&Scopes, + llvm::SmallVector &&ParamTypes, + llvm::DenseMap &&Params) + : P(P), Loc(F->getBeginLoc()), F(F), FrameSize(FrameSize), ArgSize(ArgSize), + Code(std::move(Code)), SrcMap(std::move(SrcMap)), + Scopes(std::move(Scopes)), ParamTypes(std::move(ParamTypes)), + Params(std::move(Params)) {} + +CodePtr Function::getCodeBegin() const { return Code.data(); } + +CodePtr Function::getCodeEnd() const { return Code.data() + Code.size(); } + +Function::ParamDescriptor Function::getParamDescriptor(unsigned Offset) const { + auto It = Params.find(Offset); + assert(It != Params.end() && "Invalid parameter offset"); + return It->second; +} + +SourceInfo Function::getSource(CodePtr PC) const { + unsigned Offset = PC - getCodeBegin(); + using Elem = std::pair; + auto It = std::lower_bound(SrcMap.begin(), SrcMap.end(), Elem{Offset, {}}, + [](Elem A, Elem B) { return A.first < B.first; }); + if (It == SrcMap.end() || It->first != Offset) + llvm::report_fatal_error("missing source location"); + return It->second; +} diff --git a/clang/lib/AST/Interp/Integral.h b/clang/lib/AST/Interp/Integral.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Integral.h @@ -0,0 +1,249 @@ +//===--- Integral.h - Wrapper for numeric types for the VM ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the VM types and helpers operating on types. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_NUMBER_H +#define LLVM_CLANG_AST_INTERP_NUMBER_H + +#include "clang/AST/ComparisonCategories.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" +#include +#include + +namespace clang { +namespace interp { + +using APInt = llvm::APInt; +using APSInt = llvm::APSInt; + +/// Helper to compare two comparable types. +template +ComparisonCategoryResult Compare(const T &X, const T &Y) { + if (X < Y) + return ComparisonCategoryResult::Less; + if (X > Y) + return ComparisonCategoryResult::Greater; + return ComparisonCategoryResult::Equal; +} + +/// Wrapper around numeric types. +/// +/// These wrappers are required to shared an interface between APSint and +/// builtin primitive numeral types, allowing opcodes operating on fixed +/// precision integers and fast integers to share an implementation. +template class Integral { +private: + template friend class Integral; + + // Helper structure to select the representation. + template struct Repr; + template <> struct Repr<1, false> { using Type = bool; }; + template <> struct Repr<8, false> { using Type = uint8_t; }; + template <> struct Repr<16, false> { using Type = uint16_t; }; + template <> struct Repr<32, false> { using Type = uint32_t; }; + template <> struct Repr<64, false> { using Type = uint64_t; }; + template <> struct Repr<8, true> { using Type = int8_t; }; + template <> struct Repr<16, true> { using Type = int16_t; }; + template <> struct Repr<32, true> { using Type = int32_t; }; + template <> struct Repr<64, true> { using Type = int64_t; }; + + /// Helper structure to select the min value. + template struct Min { + using Type = typename Repr::Type; + static const auto Value = std::numeric_limits::min(); + }; + template <> struct Min<1, false> { static const bool Value = false; }; + + // The primitive representing the integral. + using T = typename Repr::Type; + T V; + + /// Construct an integral from anything that is convertible to storage. + template explicit Integral(T V) : V(V) {} + +public: + /// Zero-initializes an integral. + Integral() : V(0) {} + + /// Constructs an integral from another integral. + template + explicit Integral(Integral V) : V(V.V) {} + + /// Construct an integral from a value based on signedness. + explicit Integral(const APSInt &V) + : V(V.isSigned() ? V.getSExtValue() : V.getZExtValue()) {} + + bool operator<(Integral RHS) const { return V < RHS.V; } + bool operator>(Integral RHS) const { return V > RHS.V; } + bool operator<=(Integral RHS) const { return V <= RHS.V; } + bool operator>=(Integral RHS) const { return V >= RHS.V; } + bool operator==(Integral RHS) const { return V == RHS.V; } + bool operator!=(Integral RHS) const { return V != RHS.V; } + + Integral operator+(Integral RHS) const { return Integral(V + RHS.V); } + Integral operator-(Integral RHS) const { return Integral(V - RHS.V); } + Integral operator*(Integral RHS) const { return Integral(V * RHS.V); } + Integral operator/(Integral RHS) const { return Integral(V / RHS.V); } + Integral operator%(Integral RHS) const { return Integral(V % RHS.V); } + Integral operator&(Integral RHS) const { return Integral(V & RHS.V); } + Integral operator|(Integral RHS) const { return Integral(V | RHS.V); } + Integral operator^(Integral RHS) const { return Integral(V ^ RHS.V); } + + Integral operator-() const { return Integral(-V); } + Integral operator~() const { return Integral(~V); } + + Integral operator>>(unsigned RHS) const { return Integral(V >> RHS); } + Integral operator<<(unsigned RHS) const { return Integral(V << RHS); } + + template + explicit operator Integral() const { + return Integral(V); + } + + explicit operator off_t() const { return V; } + explicit operator unsigned() const { return V; } + explicit operator uint64_t() const { return V; } + + APSInt toAPSInt() const { return APSInt(APInt(Bits, V, Signed), !Signed); } + APSInt toAPSInt(unsigned NumBits) const { + return APSInt(APInt(NumBits, V, Signed), !Signed); + } + + Integral toUnsigned() const { + return Integral(*this); + } + + unsigned bitWidth() const { return Bits; } + + bool isZero() const { return !V; } + + bool isMin() const { return *this == min(bitWidth()); } + + bool isMinusOne() const { return Signed && V == T(-1); } + + bool isSigned() const { return Signed; } + + bool isNegative() const { return V < T(0); } + + ComparisonCategoryResult compare(const Integral &RHS) const { + return Compare(V, RHS.V); + } + + unsigned countLeadingZeros() const { + unsigned LeadingZeros = __builtin_clzll(V); + constexpr auto FullBits = std::numeric_limits::digits; + return LeadingZeros - (FullBits - bitWidth()); + } + + void print(llvm::raw_ostream &OS) const { OS << V; } + + static Integral min(unsigned NumBits) { + return Integral(Min::Value); + } + + template + static typename std::enable_if::value, Integral>::type + from(T Value) { + return Integral(Value); + } + + template + static typename std::enable_if::type + from(Integral Value) { + return Integral(Value.V); + } + + template static Integral from(Integral<0, SrcSign> Value) { + if (SrcSign) + return Integral(Value.V.getSExtValue()); + else + return Integral(Value.V.getZExtValue()); + } + + static Integral zero() { return from(0); } + + template static Integral from(T Value, unsigned NumBits) { + return Integral(Value); + } + + static bool increment(Integral A, Integral *R) { + return add(A, Integral(T(1)), A.bitWidth(), R); + } + + static bool decrement(Integral A, Integral *R) { + return sub(A, Integral(T(1)), A.bitWidth(), R); + } + + static bool add(Integral A, Integral B, unsigned OpBits, Integral *R) { + return CheckAddUB(A.V, B.V, R->V); + } + + static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) { + return CheckSubUB(A.V, B.V, R->V); + } + + static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) { + return CheckMulUB(A.V, B.V, R->V); + } + +private: + template + static typename std::enable_if::value, bool>::type + CheckAddUB(T A, T B, T &R) { + return llvm::AddOverflow(A, B, R); + } + + template + static typename std::enable_if::value, bool>::type + CheckAddUB(T A, T B, T &R) { + R = A + B; + return false; + } + + template + static typename std::enable_if::value, bool>::type + CheckSubUB(T A, T B, T &R) { + return llvm::SubOverflow(A, B, R); + } + + template + static typename std::enable_if::value, bool>::type + CheckSubUB(T A, T B, T &R) { + R = A - B; + return false; + } + + template + static typename std::enable_if::value, bool>::type + CheckMulUB(T A, T B, T &R) { + return llvm::MulOverflow(A, B, R); + } + + template + static typename std::enable_if::value, bool>::type + CheckMulUB(T A, T B, T &R) { + R = A * B; + return false; + } +}; + +template +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Integral I) { + I.print(OS); + return OS; +} + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Interp.h b/clang/lib/AST/Interp/Interp.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Interp.h @@ -0,0 +1,455 @@ +//===--- Interp.h - Interpreter for the constexpr VM ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Definition of the interpreter state and entry point. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERP_H +#define LLVM_CLANG_AST_INTERP_INTERP_H + +#include "Function.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "InterpState.h" +#include "Opcode.h" +#include "Program.h" +#include "State.h" +#include "Type.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/CXXInheritance.h" +#include "clang/AST/Expr.h" +#include "llvm/ADT/APFloat.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/Support/Endian.h" +#include +#include + +namespace clang { +namespace interp { + +using APInt = llvm::APInt; +using APSInt = llvm::APSInt; + +/// Convers a value to an APValue. +template bool ReturnValue(const T &V, APValue &R) { + R = APValue(V.toAPSInt()); + return true; +} + + +template <> inline bool ReturnValue(const Pointer &Ptr, APValue &R) { + if (const auto &Value = Ptr.toAPValue()) { + R = *Value; + return true; + } + return false; +} + +/// Checks if a pointer is live and accesible. +bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK); + +/// Checks if a pointer is null. +bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + CheckSubobjectKind CSK); + +/// Checks if a pointer is in range. +bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK); + +/// Checks if a pointer points to a mutable location. +bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +// Checks a pointer offset. +bool CheckOffset(int64_t NewOffset, const Pointer &Ptr, InterpState &S, + CodePtr OpPC); + +/// Checks if a value can be loaded from a block. +bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a value can be stored in a block. +bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a value can be initialized. +bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +template inline bool IsTrue(const T &V) { return !V.isZero(); } +template <> inline bool IsTrue(const Pointer &V) { return !V.isNull(); } + +//===----------------------------------------------------------------------===// +// Add, Sub, Mul +//===----------------------------------------------------------------------===// + +template class OpAP> +bool AddSubMulHelper(InterpState &S, CodePtr OpPC, unsigned Bits, const T &LHS, + const T &RHS) { + // Fast path - add the numbers with fixed width. + T Result; + if (!OpFW(LHS, RHS, Bits, &Result)) { + S.Stk.push(Result); + return true; + } + + // If for some reason evaluation continues, use the truncated results. + S.Stk.push(Result); + + // Slow path - compute the result using another bit of precision. + APSInt Value = OpAP()(LHS.toAPSInt(Bits), RHS.toAPSInt(Bits)); + + // Report undefined behaviour, stopping if required. + const Expr *E = S.Current->getExpr(OpPC); + QualType Type = E->getType(); + if (S.checkingForOverflow()) { + auto Trunc = Value.trunc(Result.bitWidth()).toString(10); + auto Loc = E->getExprLoc(); + S.report(Loc, diag::warn_integer_constant_overflow) << Trunc << Type; + return true; + } else { + S.CCEDiag(E, diag::note_constexpr_overflow) << Value << Type; + return S.noteUndefinedBehavior(); + } +} + +template ::T> +bool Add(InterpState &S, CodePtr OpPC) { + const T &RHS = S.Stk.pop(); + const T &LHS = S.Stk.pop(); + const unsigned Bits = RHS.bitWidth() + 1; + return AddSubMulHelper(S, OpPC, Bits, LHS, RHS); +} + +template ::T> +bool Sub(InterpState &S, CodePtr OpPC) { + const T &RHS = S.Stk.pop(); + const T &LHS = S.Stk.pop(); + const unsigned Bits = RHS.bitWidth() + 1; + return AddSubMulHelper(S, OpPC, Bits, LHS, RHS); +} + +template ::T> +bool Mul(InterpState &S, CodePtr OpPC) { + const T &RHS = S.Stk.pop(); + const T &LHS = S.Stk.pop(); + const unsigned Bits = RHS.bitWidth() * 2; + return AddSubMulHelper(S, OpPC, Bits, LHS, RHS); +} + +//===----------------------------------------------------------------------===// +// Div, Rem +//===----------------------------------------------------------------------===// + +template +bool DivRemHelper(InterpState &S, CodePtr OpPC) { + const T RHS = S.Stk.pop(); + const T LHS = S.Stk.pop(); + + // Bail on division by zero. + if (RHS.isZero()) { + S.FFDiag(S.Current->getSource(OpPC), diag::note_expr_divide_by_zero); + return false; + } + + if (RHS.isSigned()) { + // (-MAX - 1) / -1 = MAX + 1 overflows. + if (LHS.isMin() && RHS.isMinusOne()) { + // Push the truncated value in case the interpreter continues. + S.Stk.push(T::min(RHS.bitWidth())); + + // Compute the actual value for the diagnostic. + const size_t Bits = RHS.bitWidth() + 1; + APSInt Value = OpAP()(LHS.toAPSInt(Bits), RHS.toAPSInt(Bits)); + return S.reportOverflow(S.Current->getExpr(OpPC), Value); + } + } + + // Safe to execute division here. + S.Stk.push(OpFW(LHS, RHS)); + return true; +} + +template T DivFn(T a, T b) { return a / b; } + +template T RemFn(T a, T b) { return a % b; } + +template ::T> +bool Div(InterpState &S, CodePtr OpPC) { + return DivRemHelper, std::divides>(S, OpPC); +} + +template ::T> +bool Rem(InterpState &S, CodePtr OpPC) { + return DivRemHelper, std::modulus>(S, OpPC); +} + +//===----------------------------------------------------------------------===// +// EQ, NE, GT, GE, LT, LE +//===----------------------------------------------------------------------===// + +using CompareFn = llvm::function_ref; + +template +bool CmpHelper(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv::T; + const T &RHS = S.Stk.pop(); + const T &LHS = S.Stk.pop(); + S.Stk.push(BoolT::from(Fn(LHS.compare(RHS)))); + return true; +} + +template <> +inline bool CmpHelper(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv::T; + const Pointer &RHS = S.Stk.pop(); + const Pointer &LHS = S.Stk.pop(); + + if (!Pointer::isComparable(LHS, RHS)) { + const auto &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr); + return false; + } else { + auto VL = LHS.getOffset(); + auto VR = RHS.getOffset(); + S.Stk.push(BoolT::from(Fn(Compare(VL, VR)))); + return true; + } +} + +template ::T> +bool EQ(InterpState &S, CodePtr OpPC) { + return CmpHelper(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Equal; + }); +} + +template ::T> +bool NE(InterpState &S, CodePtr OpPC) { + return CmpHelper(S, OpPC, [](ComparisonCategoryResult R) { + return R != ComparisonCategoryResult::Equal; + }); +} + +template ::T> +bool LT(InterpState &S, CodePtr OpPC) { + return CmpHelper(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Less; + }); +} + +template ::T> +bool LE(InterpState &S, CodePtr OpPC) { + return CmpHelper(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Less || + R == ComparisonCategoryResult::Equal; + }); +} + +template ::T> +bool GT(InterpState &S, CodePtr OpPC) { + return CmpHelper(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Greater; + }); +} + +template ::T> +bool GE(InterpState &S, CodePtr OpPC) { + return CmpHelper(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Greater || + R == ComparisonCategoryResult::Equal; + }); +} + +//===----------------------------------------------------------------------===// +// Dup, Pop +//===----------------------------------------------------------------------===// + +template ::T> +bool Dup(InterpState &S, CodePtr OpPC) { + S.Stk.push(S.Stk.peek()); + return true; +} + +template ::T> +bool Pop(InterpState &S, CodePtr OpPC) { + S.Stk.pop(); + return true; +} + +//===----------------------------------------------------------------------===// +// Test +//===----------------------------------------------------------------------===// +template ::T> +bool Test(InterpState &S, CodePtr OpPC) { + S.Stk.push(IsTrue(S.Stk.pop())); + return true; +} + +//===----------------------------------------------------------------------===// +// Const, ConstFP +//===----------------------------------------------------------------------===// + +template ::T> +bool Const(InterpState &S, CodePtr OpPC, const T &Arg) { + S.Stk.push(Arg); + return true; +} + +//===----------------------------------------------------------------------===// +// Get/Set Local/Param/Global/This +//===----------------------------------------------------------------------===// + +template ::T> +bool GetLocal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Stk.push(S.Current->getLocal(I)); + return true; +} + +template ::T> +bool SetLocal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->setLocal(I, S.Stk.pop()); + return true; +} + +template ::T> +bool GetParam(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) { + return false; + } + S.Stk.push(S.Current->getParam(I)); + return true; +} + +template ::T> +bool SetParam(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->setParam(I, S.Stk.pop()); + return true; +} + +//===----------------------------------------------------------------------===// +// GetPtr Local/Param/Global/Field/This +//===----------------------------------------------------------------------===// + +inline bool GetPtrLocal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Stk.push(S.Current->getLocalPointer(I)); + return true; +} + +inline bool GetPtrParam(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) { + return false; + } + S.Stk.push(S.Current->getParamPointer(I)); + return true; +} + +//===----------------------------------------------------------------------===// +// Load, Store, Init +//===----------------------------------------------------------------------===// + +template ::T> +bool Load(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.peek(); + if (!CheckLoad(S, OpPC, Ptr)) + return false; + S.Stk.push(Ptr.deref()); + return true; +} + +template ::T> +bool LoadPop(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.pop(); + if (!CheckLoad(S, OpPC, Ptr)) + return false; + S.Stk.push(Ptr.deref()); + return true; +} + +template ::T> +bool Store(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.peek(); + if (!CheckStore(S, OpPC, Ptr)) + return false; + Ptr.deref() = Value; + return true; +} + +template ::T> +bool StorePop(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.pop(); + if (!CheckStore(S, OpPC, Ptr)) + return false; + Ptr.deref() = Value; + return true; +} + +template ::T> +bool Init(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.peek(); + if (!CheckInit(S, OpPC, Ptr)) { + return false; + } + Ptr.deref() = Value; + return true; +} + +//===----------------------------------------------------------------------===// +// Destroy +//===----------------------------------------------------------------------===// + +inline bool Destroy(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->destroy(I); + return true; +} + +//===----------------------------------------------------------------------===// +// Zero, Nullptr +//===----------------------------------------------------------------------===// + +template ::T> +bool Zero(InterpState &S, CodePtr OpPC) { + S.Stk.push(T::zero()); + return true; +} + +inline bool NullPtr(InterpState &S, CodePtr OpPC) { + S.Stk.push(); + return true; +} + +//===----------------------------------------------------------------------===// +// Undef +//===----------------------------------------------------------------------===// + +inline bool Undef(InterpState &S, CodePtr OpPC) { + // this should generate a dummy pointer, but nullptr works. + S.Stk.push(); + return true; +} + +//===----------------------------------------------------------------------===// +// NoRet +//===----------------------------------------------------------------------===// + +inline bool NoRet(InterpState &S, CodePtr OpPC) { + SourceLocation EndLoc = S.Current->getCallee()->getEndLoc(); + S.FFDiag(EndLoc, diag::note_constexpr_no_return); + return false; +} + +/// Interpreter entry point. +bool Interpret(InterpState &S, APValue &Result); + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Interp.cpp b/clang/lib/AST/Interp/Interp.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Interp.cpp @@ -0,0 +1,239 @@ +//===--- InterpState.cpp - Interpreter for the constexpr VM -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Interp.h" +#include "Function.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "Opcode.h" +#include "Program.h" +#include "State.h" +#include "Type.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/CXXInheritance.h" +#include "clang/AST/Expr.h" +#include "llvm/ADT/APSInt.h" +#include +#include + +using namespace clang; +using namespace clang::interp; + +//===----------------------------------------------------------------------===// +// Ret +//===----------------------------------------------------------------------===// + +template ::T> +static bool Ret(InterpState &S, CodePtr &PC, APValue &Result) { + S.CallStackDepth--; + const T &Ret = S.Stk.pop(); + + assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame"); + if (!S.checkingPotentialConstantExpression()) + S.Current->popArgs(); + + if (InterpFrame *Caller = S.Current->Caller) { + PC = S.Current->getRetPC(); + delete S.Current; + S.Current = Caller; + S.Stk.push(Ret); + } else { + delete S.Current; + S.Current = nullptr; + if (!ReturnValue(Ret, Result)) + return false; + } + return true; +} + +static bool RetVoid(InterpState &S, CodePtr &PC, APValue &Result) { + S.CallStackDepth--; + + assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame"); + if (!S.checkingPotentialConstantExpression()) + S.Current->popArgs(); + + if (InterpFrame *Caller = S.Current->Caller) { + PC = S.Current->getRetPC(); + delete S.Current; + S.Current = Caller; + } else { + delete S.Current; + S.Current = nullptr; + } + return true; +} + +//===----------------------------------------------------------------------===// +// Jmp, Jt, Jf +//===----------------------------------------------------------------------===// + +static bool Jmp(InterpState &S, CodePtr &PC, int32_t Offset) { + PC += Offset; + return true; +} + +static bool Jt(InterpState &S, CodePtr &PC, int32_t Offset) { + if (S.Stk.pop()) { + PC += Offset; + } + return true; +} + +static bool Jf(InterpState &S, CodePtr &PC, int32_t Offset) { + if (!S.Stk.pop()) { + PC += Offset; + } + return true; +} + +namespace clang { +namespace interp { + +bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + const auto &Src = S.Current->getSource(OpPC); + if (Ptr.isNull()) { + + if (Ptr.isField()) + S.FFDiag(Src, diag::note_constexpr_null_subobject) << CSK_Field; + else + S.FFDiag(Src, diag::note_constexpr_access_null) << AK; + + return false; + } + + if (!Ptr.isLive()) { + bool IsTemp = Ptr.isTemporary(); + + S.FFDiag(Src, diag::note_constexpr_lifetime_ended, 1) << AK << !IsTemp; + + if (IsTemp) + S.Note(Ptr.getDeclLoc(), diag::note_constexpr_temporary_here); + else + S.Note(Ptr.getDeclLoc(), diag::note_declared_at); + + return false; + } + + return true; +} + +bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + CheckSubobjectKind CSK) { + if (!Ptr.isNull()) + return true; + const auto &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_null_subobject) << CSK; + return false; +} + +bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + if (Ptr.inBounds()) + return true; + const auto &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_access_past_end) << AK; + return false; +} + +bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + assert(Ptr.isLive() && "Pointer is not live"); + if (Ptr.isMutable()) { + return true; + } + + const QualType Ty = Ptr.getType(); + const auto &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_modify_const_type) << Ty; + return false; +} + +bool CheckOffset(int64_t NewOffset, const Pointer &Ptr, InterpState &S, + CodePtr OpPC) { + int64_t Index = NewOffset / static_cast(Ptr.elemSize()); + size_t NumElems = Ptr.size() / Ptr.elemSize(); + + if (Index < 0 || static_cast(Index) > NumElems) { + S.CCEDiag(S.Current->getSource(OpPC), diag::note_constexpr_array_index) + << Integral<64, true>::from(Index).toAPSInt() + << /*array*/ static_cast(!Ptr.isArray()) + << static_cast(NumElems); + return false; + } + return true; +} + +static bool CheckExtern(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!Ptr.isExtern()) + return true; + + auto *VD = Ptr.getDeclDesc()->Source.dyn_cast(); + const auto &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_ltor_non_constexpr, 1) << VD; + S.Note(VD->getLocation(), diag::note_declared_at); + return false; +} + +static bool CheckInitialized(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + if (Ptr.isInitialized()) + return true; + const auto &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_access_uninit) << AK << false; + return false; +} + +bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckExtern(S, OpPC, Ptr)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckInitialized(S, OpPC, Ptr, AK_Read)) + return false; + return true; +} + +bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_Assign)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Assign)) + return false; + if (!CheckMutable(S, OpPC, Ptr)) + return false; + return true; +} + +bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_Assign)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Assign)) + return false; + return true; +} + +bool Interpret(InterpState &S, APValue &Result) { + CodePtr PC = S.Current->getPC(); + + for (;;) { + auto Op = PC.read(); + CodePtr OpPC = PC; + + switch (Op) { +#define GET_INTERP +#include "Opcodes.inc" +#undef GET_INTERP + } + } +} + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/InterpFrame.h b/clang/lib/AST/Interp/InterpFrame.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/InterpFrame.h @@ -0,0 +1,153 @@ +//===--- InterpFrame.h - Call Frame implementation for the VM ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the class storing information about stack frames in the interpreter. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERPFRAME_H +#define LLVM_CLANG_AST_INTERP_INTERPFRAME_H + +#include "Frame.h" +#include "Pointer.h" +#include "Program.h" +#include "State.h" +#include +#include + +namespace clang { +namespace interp { +class Function; +class InterpState; + +/// Frame storing local variables. +class InterpFrame final : public Frame { +public: + /// The frame of the previous function. + InterpFrame *Caller; + + /// Creates a new frame for a method call. + InterpFrame(InterpState &S, Function *Func, InterpFrame *Caller, + CodePtr RetPC, const Pointer &This); + + /// Destroys the frame, killing all live pointers to stack slots. + ~InterpFrame(); + + /// Invokes the destructors for a scope. + void destroy(unsigned Idx); + + /// Pops the arguments off the stack. + void popArgs(); + + /// Describes the frame with arguments for diagnostic purposes. + void describe(llvm::raw_ostream &OS); + + /// Returns the parent frame object. + Frame *getCaller() const; + + /// Returns the location of the call to the frame. + SourceLocation getCallLocation() const; + + /// Returns the caller. + const FunctionDecl *getCallee() const; + + /// Returns the current function. + Function *getFunction() const { return Func; } + + /// Returns the offset on the stack at which the frame starts. + size_t getFrameOffset() const { return FrameOffset; } + + /// Returns the value of a local variable. + template const T &getLocal(unsigned Offset) { + return localRef(Offset); + } + + /// Mutates a local variable. + template void setLocal(unsigned Offset, const T &Value) { + localRef(Offset) = Value; + } + + /// Returns a pointer to a local variables. + Pointer getLocalPointer(unsigned Offset); + + /// Returns the value of an argument. + template const T &getParam(unsigned Offset) { + auto Pt = Params.find(Offset); + if (Pt == Params.end()) { + return stackRef(Offset); + } else { + return Pointer(reinterpret_cast(Pt->second.get())).deref(); + } + } + + /// Mutates a local copy of a parameter. + template void setParam(unsigned Offset, const T &Value) { + getParamPointer(Offset).deref() = Value; + } + + /// Returns a pointer to an argument - lazily creates a block. + Pointer getParamPointer(unsigned Offset); + + /// Returns the 'this' pointer. + const Pointer &getThis() const { return This; } + + /// Checks if the frame is a root frame - return should quit the interpreter. + bool isRoot() const { return !Func; } + + /// Returns the PC of the frame's code start. + CodePtr getPC() const { return Func->getCodeBegin(); } + + /// Returns the return address of the frame. + CodePtr getRetPC() const { return RetPC; } + + /// Map a location to a source. + virtual SourceInfo getSource(CodePtr PC) const; + const Expr *getExpr(CodePtr PC) const; + SourceLocation getLocation(CodePtr PC) const; + +private: + /// Returns an original argument from the stack. + template const T &stackRef(unsigned Offset) { + return *reinterpret_cast(Args - ArgSize + Offset); + } + + /// Returns an offset to a local. + template T &localRef(unsigned Offset) { + return *reinterpret_cast(Locals.get() + Offset); + } + + /// Returns a pointer to a local's block. + void *localBlock(unsigned Offset) { + return Locals.get() + Offset - sizeof(Block); + } + +private: + /// Reference to the interpreter state. + InterpState &S; + /// Reference to the function being executed. + Function *Func; + /// Current object pointer for methods. + Pointer This; + /// Return address. + CodePtr RetPC; + /// The size of all the arguments. + const unsigned ArgSize; + /// Pointer to the arguments in the callee's frame. + char *Args = nullptr; + /// Fixed, initial storage for known local variables. + std::unique_ptr Locals; + /// Offset on the stack at entry. + const size_t FrameOffset; + /// Mapping from arg offsets to their argument blocks. + llvm::DenseMap> Params; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/InterpFrame.cpp b/clang/lib/AST/Interp/InterpFrame.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/InterpFrame.cpp @@ -0,0 +1,178 @@ +//===--- InterpFrame.cpp - Call Frame implementation for the VM -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "InterpFrame.h" +#include "Function.h" +#include "Interp.h" +#include "InterpStack.h" +#include "Program.h" +#include "Type.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +InterpFrame::InterpFrame(InterpState &S, Function *Func, InterpFrame *Caller, + CodePtr RetPC, const Pointer &This) + : Caller(Caller), S(S), Func(Func), This(This), RetPC(RetPC), + ArgSize(Func ? Func->getArgSize() : 0), + Args(static_cast(S.Stk.top())), FrameOffset(S.Stk.size()) { + if (Func) { + if (auto FrameSize = Func->getFrameSize()) { + Locals = llvm::make_unique(FrameSize); + for (auto &Scope : Func->scopes()) { + for (auto &Local : Scope.locals()) { + Block *B = new (localBlock(Local.Offset)) Block(Local.Desc); + if (Local.Desc->CtorFn) + Local.Desc->CtorFn(B, B->data(), Local.Desc->IsMutable, Local.Desc); + } + } + } + } +} + +InterpFrame::~InterpFrame() { + for (auto &Param : Params) { + S.deallocate(reinterpret_cast(Param.second.get())); + } +} + +void InterpFrame::destroy(unsigned Idx) { + for (auto &Local : Func->getScope(Idx).locals()) { + S.deallocate(reinterpret_cast(localBlock(Local.Offset))); + } +} + +void InterpFrame::popArgs() { + for (PrimType Ty : Func->args_reverse()) + TYPE_SWITCH(Ty, S.Stk.discard()); +} + +template +static void print(llvm::raw_ostream &OS, const T &V, ASTContext &, bool) { + OS << V; +} + +template <> +void print(llvm::raw_ostream &OS, const Pointer &P, ASTContext &Ctx, + bool IsReference) { + if (P.isNull()) { + OS << "nullptr"; + return; + } + + auto printDesc = [&OS, &Ctx](Descriptor *Desc) { + if (auto *D = Desc->Source.dyn_cast()) { + OS << *D; + return; + } + if (auto *E = Desc->Source.dyn_cast()) { + E->printPretty(OS, nullptr, Ctx.getPrintingPolicy()); + return; + } + llvm_unreachable("Invalid descriptor type"); + }; + + if (!IsReference) + OS << "&"; + llvm::SmallVector Levels; + for (Pointer F = P; F.isField(); F = F.getBase()) + Levels.push_back(F); + + printDesc(P.getDeclDesc()); + for (auto It = Levels.rbegin(); It != Levels.rend(); ++It) { + OS << "."; + printDesc(It->getFieldDesc()); + } + + if (auto Index = P.getIndex()) + OS << " + " << Index; +} + +void InterpFrame::describe(llvm::raw_ostream &OS) { + auto *F = getCallee(); + auto *M = dyn_cast(F); + if (M && M->isInstance() && !isa(F)) { + print(OS, This, S.getCtx(), /*isReference*/false); + OS << "->"; + } + OS << *F << "("; + unsigned Off = 0; + for (unsigned I = 0, N = F->getNumParams(); I < N; ++I) { + QualType Ty = F->getParamDecl(I)->getType(); + const bool IsReference = Ty->isReferenceType(); + + PrimType PrimTy; + if (auto T = S.Ctx.classify(Ty)) { + PrimTy = *T; + } else { + PrimTy = PT_Ptr; + } + + TYPE_SWITCH(PrimTy, print(OS, stackRef(Off), S.getCtx(), IsReference)); + Off += align(primSize(PrimTy)); + if (I + 1 != N) + OS << ", "; + } + OS << ")"; +} + +Frame *InterpFrame::getCaller() const { + if (Caller->Caller) + return Caller; + return S.getSplitFrame(); +} + +SourceLocation InterpFrame::getCallLocation() const { + if (!Caller->Func) + return S.getLocation(nullptr, {}); + return S.getLocation(Caller->Func, RetPC - sizeof(uintptr_t)); +} + +const FunctionDecl *InterpFrame::getCallee() const { + return Func->getDecl(); +} + +Pointer InterpFrame::getLocalPointer(unsigned Offset) { + assert(Offset < Func->getFrameSize() && "Invalid local offset."); + return Pointer( + reinterpret_cast(Locals.get() + Offset - sizeof(Block))); +} + +Pointer InterpFrame::getParamPointer(unsigned Off) { + // Return the block if it was created previously. + auto Pt = Params.find(Off); + if (Pt != Params.end()) { + return Pointer(reinterpret_cast(Pt->second.get())); + } + + // Allocate memory to store the parameter and the block metadata. + const auto &Desc = Func->getParamDescriptor(Off); + auto Memory = llvm::make_unique(sizeof(Block) + Desc.second->Size); + auto *B = new (Memory.get()) Block(Desc.second); + + // Copy the initial value. + TYPE_SWITCH(Desc.first, new (B->data()) T(stackRef(Off))); + + // Record the param. + Params.insert({Off, std::move(Memory)}); + return Pointer(B); +} + +SourceInfo InterpFrame::getSource(CodePtr PC) const { + return S.getSource(Func, PC); +} + +const Expr *InterpFrame::getExpr(CodePtr PC) const { + return S.getExpr(Func, PC); +} + +SourceLocation InterpFrame::getLocation(CodePtr PC) const { + return S.getLocation(Func, PC); +} + diff --git a/clang/lib/AST/Interp/InterpStack.h b/clang/lib/AST/Interp/InterpStack.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/InterpStack.h @@ -0,0 +1,113 @@ +//===--- InterpStack.h - Stack implementation for the VM --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the upwards-growing stack used by the interpreter. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H +#define LLVM_CLANG_AST_INTERP_INTERPSTACK_H + +#include + +namespace clang { +namespace interp { + +/// Stack frame storing temporaries and parameters. +class InterpStack final { +public: + InterpStack() {} + + /// Destroys the stack, freeing up storage. + ~InterpStack(); + + /// Constructs a value in place on the top of the stack. + template void push(Tys &&... Args) { + new (grow(aligned_size())) T(std::forward(Args)...); + } + + /// Returns the value from the top of the stack and removes it. + template T pop() { + auto *Ptr = &peek(); + auto Value = std::move(*Ptr); + Ptr->~T(); + shrink(aligned_size()); + return Value; + } + + /// Discards the top value from the stack. + template void discard() { + auto *Ptr = &peek(); + Ptr->~T(); + shrink(aligned_size()); + } + + /// Returns a reference to the value on the top of the stack. + template T &peek() { + return *reinterpret_cast(peek(aligned_size())); + } + + /// Returns a pointer to the top object. + void *top() { return Chunk ? peek(0) : nullptr; } + + /// Returns the size of the stack in bytes. + size_t size() const { return StackSize; } + + /// Clears the stack without calling any destructors. + void clear(); + +private: + /// All stack slots are aligned to the native pointer alignment for storage. + template constexpr size_t aligned_size() const { + static_assert(alignof(void *) % alignof(T) == 0, "invalid alignment"); + return ((sizeof(T) + alignof(void *) - 1) / alignof(void *)) * + alignof(void *); + } + + /// Grows the stack to accomodate a value and returns a pointer to it. + void *grow(size_t Size); + /// Returns a pointer from the top of the stack. + void *peek(size_t Size); + /// Shrinks the stack. + void shrink(size_t Size); + + /// Allocate stack space in 1Mb chunks. + static constexpr size_t ChunkSize = 1024 * 1024; + + /// Metadata for each stack chunk. + /// + /// The stack is composed of a linked list of chunks. Whenever an allocation + /// is out of bounds, a new chunk is linked. When a chunk becomes empty, + /// it is not immediately freed: a chunk is deallocated only when the + /// predecessor becomes empty. + struct StackChunk { + StackChunk *Next; + StackChunk *Prev; + char *End; + + StackChunk(StackChunk *Prev = nullptr) + : Next(nullptr), Prev(Prev), End(reinterpret_cast(this + 1)) {} + + /// Returns the size of the chunk, minus the header. + size_t size() { return End - start(); } + + /// Returns a pointer to the start of the data region. + char *start() { return reinterpret_cast(this + 1); } + }; + static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size"); + + /// First chunk on the stack. + StackChunk *Chunk = nullptr; + /// Total size of the stack. + size_t StackSize = 0; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/InterpStack.cpp b/clang/lib/AST/Interp/InterpStack.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/InterpStack.cpp @@ -0,0 +1,76 @@ +//===--- InterpStack.cpp - Stack implementation for the VM ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "InterpStack.h" + +using namespace clang; +using namespace clang::interp; + +InterpStack::~InterpStack() { + clear(); +} + +void InterpStack::clear() { + if (Chunk && Chunk->Next) + free(Chunk->Next); + if (Chunk) + free(Chunk); + Chunk = nullptr; + StackSize = 0; +} + +void *InterpStack::grow(size_t Size) { + assert(Size < ChunkSize - sizeof(StackChunk) && "Object too large"); + + if (!Chunk || sizeof(StackChunk) + Chunk->size() + Size > ChunkSize) { + if (Chunk && Chunk->Next) { + Chunk = Chunk->Next; + } else { + StackChunk *Next = new (malloc(ChunkSize)) StackChunk(Chunk); + if (Chunk) + Chunk->Next = Next; + Chunk = Next; + } + } + + auto Object = Chunk->End; + Chunk->End += Size; + StackSize += Size; + return reinterpret_cast(Object); +} + +void *InterpStack::peek(size_t Size) { + assert(Chunk && "Stack is empty!"); + + StackChunk *Ptr = Chunk; + while (Size > Ptr->size()) { + Size -= Ptr->size(); + Ptr = Ptr->Prev; + assert(Ptr && "Offset too large"); + } + + return reinterpret_cast(Ptr->End - Size); +} + +void InterpStack::shrink(size_t Size) { + assert(Chunk && "Chunk is empty!"); + + while (Size > Chunk->size()) { + Size -= Chunk->size(); + if (Chunk->Next) { + free(Chunk->Next); + Chunk->Next = nullptr; + } + Chunk->End = Chunk->start(); + Chunk = Chunk->Prev; + assert(Chunk && "Offset too large"); + } + + Chunk->End -= Size; + StackSize -= Size; +} diff --git a/clang/lib/AST/Interp/InterpState.h b/clang/lib/AST/Interp/InterpState.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/InterpState.h @@ -0,0 +1,109 @@ +//===--- InterpState.h - Interpreter state for the constexpr VM -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Definition of the interpreter state and entry point. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERPSTATE_H +#define LLVM_CLANG_AST_INTERP_INTERPSTATE_H + +#include "Context.h" +#include "Function.h" +#include "InterpStack.h" +#include "State.h" +#include "clang/AST/APValue.h" +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/Expr.h" +#include "clang/Basic/OptionalDiagnostic.h" + +namespace clang { +namespace interp { +class Context; +class Function; +class InterpStack; +class InterpFrame; +class SourceMapper; + +/// Interpreter context. +class InterpState final : public State, public SourceMapper { +public: + InterpState(State &Parent, Program &P, InterpStack &Stk, Context &Ctx, + SourceMapper *M = nullptr); + + ~InterpState(); + + // Stack frame accessors. + Frame *getSplitFrame() { return Parent.getCurrentFrame(); } + Frame *getCurrentFrame() override; + unsigned getCallStackDepth() override { return CallStackDepth; } + const Frame *getBottomFrame() const override { + return Parent.getBottomFrame(); + } + + // Acces objects from the walker context. + Expr::EvalStatus &getEvalStatus() const override { + return Parent.getEvalStatus(); + } + ASTContext &getCtx() const override { return Parent.getCtx(); } + + // Forward status checks and updates to the walker. + bool checkingForOverflow() const override { + return Parent.checkingForOverflow(); + } + bool checkingPotentialConstantExpression() const override { + return Parent.checkingPotentialConstantExpression(); + } + bool noteUndefinedBehavior() override { + return Parent.noteUndefinedBehavior(); + } + bool hasActiveDiagnostic() override { return Parent.hasActiveDiagnostic(); } + void setActiveDiagnostic(bool Flag) override { + Parent.setActiveDiagnostic(Flag); + } + void setFoldFailureDiagnostic(bool Flag) override { + Parent.setFoldFailureDiagnostic(Flag); + } + bool hasPriorDiagnostic() override { return Parent.hasPriorDiagnostic(); } + + /// Reports overflow and return true if evaluation should continue. + bool reportOverflow(const Expr *E, const llvm::APSInt &Value); + + /// Deallocates a pointer. + void deallocate(Block *B); + + /// Delegates source mapping to the mapper. + SourceInfo getSource(Function *F, CodePtr PC) const override { + return M ? M->getSource(F, PC) : F->getSource(PC); + } + +private: + /// AST Walker state. + State &Parent; + /// Dead block chain. + DeadBlock *DeadBlocks = nullptr; + /// Reference to the offset-source mapping. + SourceMapper *M; + +public: + /// Reference to the module containing all bytecode. + Program &P; + /// Temporary stack. + InterpStack &Stk; + /// Interpreter Context. + Context &Ctx; + /// The current frame. + InterpFrame *Current = nullptr; + /// Call stack depth. + unsigned CallStackDepth; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/InterpState.cpp b/clang/lib/AST/Interp/InterpState.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/InterpState.cpp @@ -0,0 +1,74 @@ +//===--- InterpState.cpp - Interpreter for the constexpr VM -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "InterpState.h" +#include "Function.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "Opcode.h" +#include "Program.h" +#include "State.h" +#include "Type.h" +#include + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; + +InterpState::InterpState(State &Parent, Program &P, InterpStack &Stk, + Context &Ctx, SourceMapper *M) + : Parent(Parent), M(M), P(P), Stk(Stk), Ctx(Ctx), Current(nullptr), + CallStackDepth(Parent.getCallStackDepth() + 1) {} + +InterpState::~InterpState() { + while (Current) { + InterpFrame *Next = Current->Caller; + delete Current; + Current = Next; + } + + while (DeadBlocks) { + DeadBlock *Next = DeadBlocks->Next; + free(DeadBlocks); + DeadBlocks = Next; + } +} + +Frame *InterpState::getCurrentFrame() { + if (Current && Current->Caller) { + return Current; + } else { + return Parent.getCurrentFrame(); + } +} + +bool InterpState::reportOverflow(const Expr *E, const llvm::APSInt &Value) { + QualType Type = E->getType(); + CCEDiag(E, diag::note_constexpr_overflow) << Value << Type; + return noteUndefinedBehavior(); +} + +void InterpState::deallocate(Block *B) { + Descriptor *Desc = B->getDescriptor(); + if (B->hasPointers()) { + size_t Size = B->getSize(); + + // Allocate a new block, transferring over pointers. + char *Memory = reinterpret_cast(malloc(sizeof(DeadBlock) + Size)); + auto *D = new (Memory) DeadBlock(DeadBlocks, B); + + // Move data from one block to another. + if (Desc->MoveFn) + Desc->MoveFn(B, B->data(), D->data(), Desc); + } else { + // Free storage, if necessary. + if (Desc->DtorFn) + Desc->DtorFn(B, B->data(), Desc); + } +} diff --git a/clang/lib/AST/Interp/LinkEmitter.h b/clang/lib/AST/Interp/LinkEmitter.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/LinkEmitter.h @@ -0,0 +1,112 @@ +//===--- LinkEmitter.h - Instruction emitter for the VM ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the instruction emitters. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_LINKEMITTER_H +#define LLVM_CLANG_AST_INTERP_LINKEMITTER_H + +#include "ByteCodeGenError.h" +#include "Context.h" +#include "InterpStack.h" +#include "InterpState.h" +#include "Program.h" +#include "Source.h" +#include "Type.h" +#include "llvm/Support/Error.h" + +namespace clang { +namespace interp { +class Context; +class SourceInfo; +enum Opcode : uint32_t; + +/// An emitter which links the program to bytecode for later use. +class LinkEmitter { +protected: + using LabelTy = uint32_t; + using AddrTy = uintptr_t; + using Local = Scope::Local; + +public: + /// Compiles the function into the module. + llvm::Expected compileFunc(const FunctionDecl *F); + +protected: + LinkEmitter(Context &Ctx, State &S, Program &P) : Ctx(Ctx), P(P) {} + + virtual ~LinkEmitter() {} + + /// Define a label. + void emitLabel(LabelTy Label); + /// Create a label. + LabelTy getLabel() { return ++NextLabel; } + + /// Methods implemented by the compiler. + virtual bool compile(const FunctionDecl *E) = 0; + virtual bool compile(const Expr *E) = 0; + virtual bool compile(const VarDecl *E) = 0; + + /// Bails out if a given node cannot be compiled. + bool bail(const Stmt *S) { return bail(S->getBeginLoc()); } + bool bail(const Decl *D) { return bail(D->getBeginLoc()); } + bool bail(const SourceLocation &Loc); + + /// Emits jumps. + bool jumpTrue(const LabelTy &Label); + bool jumpFalse(const LabelTy &Label); + bool jump(const LabelTy &Label); + bool fallthrough(const LabelTy &Label) { return true; } + + /// Callback for local registration. + Local createLocal(Descriptor *D); + + /// Parameter indices. + llvm::DenseMap Params; + /// Local descriptors. + llvm::SmallVector, 2> Descriptors; + +private: + /// Current compilation context. + Context &Ctx; + /// Program to link to. + Program &P; + /// Index of the next available label. + LabelTy NextLabel = 0; + /// Offset of the next local variable. + unsigned NextLocalOffset = 0; + /// Location of a failure. + llvm::Optional BailLocation; + /// Label information for linker. + llvm::DenseMap LabelOffsets; + /// Location of label relocations. + llvm::DenseMap> LabelRelocs; + /// Program code. + std::vector Code; + /// Opcode to expression mapping. + SourceMap SrcMap; + + /// Returns the offset for a jump or records a relocation. + int32_t getOffset(LabelTy Label); + + /// Emits an opcode. + template + bool emitOp(Opcode Op, const Tys &... Args, const SourceInfo &L); + +protected: +#define GET_LINK_PROTO +#include "Opcodes.inc" +#undef GET_LINK_PROTO +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/LinkEmitter.cpp b/clang/lib/AST/Interp/LinkEmitter.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/LinkEmitter.cpp @@ -0,0 +1,157 @@ +//===--- LinkEmitter.cpp - Instruction emitter for the VM -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "LinkEmitter.h" +#include "Context.h" +#include "Opcode.h" +#include "Program.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +using Error = llvm::Error; + +Expected LinkEmitter::compileFunc(const FunctionDecl *F) { + // Set up argument indices. + unsigned ParamOffset = 0; + SmallVector ParamTypes; + llvm::DenseMap ParamDescriptors; + + // If the return is not a primitive, a pointer to the storage where the value + // is initialized in is passed as the first argument. + if (Ctx.isComposite(F->getReturnType())) { + ParamTypes.push_back(PT_Ptr); + ParamOffset += align(primSize(PT_Ptr)); + } + + // Assign descriptors to all parameters. + // Composite objects are lowered to pointers. + for (auto *PD : F->parameters()) { + PrimType Ty; + if (auto T = Ctx.classify(PD->getType())) { + Ty = *T; + } else { + Ty = PT_Ptr; + } + + auto *Desc = P.createDescriptor(PD, Ty); + ParamDescriptors.insert({ParamOffset, {Ty, Desc}}); + Params.insert({PD, ParamOffset}); + ParamOffset += align(primSize(Ty)); + ParamTypes.push_back(Ty); + } + + // Compile the function body. + if (!compile(F)) + return llvm::make_error(*BailLocation); + + // Create scopes from descriptors. + llvm::SmallVector Scopes; + for (auto &DS : Descriptors) { + Scopes.emplace_back(std::move(DS)); + } + + // Create a handle over the emitted code. + return P.createFunction(F, NextLocalOffset, ParamOffset, std::move(Code), + std::move(SrcMap), std::move(Scopes), + std::move(ParamTypes), std::move(ParamDescriptors)); +} + +Scope::Local LinkEmitter::createLocal(Descriptor *D) { + NextLocalOffset += sizeof(Block); + unsigned Location = NextLocalOffset; + NextLocalOffset += align(D->Size); + return {Location, D}; +} + +void LinkEmitter::emitLabel(LabelTy Label) { + const size_t Target = Code.size(); + LabelOffsets.insert({Label, Target}); + auto It = LabelRelocs.find(Label); + if (It != LabelRelocs.end()) { + for (unsigned Reloc : It->second) { + using namespace llvm::support; + + /// Rewrite the operand of all jumps to this label. + void *Location = Code.data() + Reloc - sizeof(int32_t); + const int32_t Offset = Target - static_cast(Reloc); + endian::write(Location, Offset); + } + LabelRelocs.erase(It); + } +} + +int32_t LinkEmitter::getOffset(LabelTy Label) { + // Compute the PC offset which the jump is relative to. + const int64_t Position = Code.size() + sizeof(Opcode) + sizeof(int32_t); + + // If target is known, compute jump offset. + auto It = LabelOffsets.find(Label); + if (It != LabelOffsets.end()) { + return It->second - Position; + } + + // Otherwise, record relocation and return dummy offset. + LabelRelocs[Label].push_back(Position); + return 0ull; +} + +bool LinkEmitter::bail(const SourceLocation &Loc) { + if (!BailLocation) + BailLocation = Loc; + return false; +} + +template +bool LinkEmitter::emitOp(Opcode Op, const Tys &... Args, const SourceInfo &SI) { + bool Success = true; + + /// Helper to write bytecode and bail out if 32-bit offsets become invalid. + auto emit = [this, &Success](const char *Data, size_t Size) { + if (Code.size() + Size > std::numeric_limits::max()) { + Success = false; + return; + } + Code.insert(Code.end(), Data, Data + Size); + }; + + /// The opcode is followed by arguments. The source info is + /// attached to the address after the opcode. + emit(reinterpret_cast(&Op), sizeof(Opcode)); + if (SI) + SrcMap.emplace_back(Code.size(), SI); + + /// The initializer list forces the expression to be evaluated + /// for each argument in the variadic template, in order. + (void)std::initializer_list{ + (emit(reinterpret_cast(&Args), sizeof(Args)), 0)...}; + + return Success; +} + +bool LinkEmitter::jumpTrue(const LabelTy &Label) { + return emitJt(getOffset(Label), {}); +} + +bool LinkEmitter::jumpFalse(const LabelTy &Label) { + return emitJf(getOffset(Label), {}); +} + +bool LinkEmitter::jump(const LabelTy &Label) { + return emitJmp(getOffset(Label), {}); +} + +//===----------------------------------------------------------------------===// +// Opcode emitters +//===----------------------------------------------------------------------===// + +#define GET_LINK_IMPL +#include "Opcodes.inc" +#undef GET_LINK_IMPL diff --git a/clang/lib/AST/Interp/Opcode.h b/clang/lib/AST/Interp/Opcode.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Opcode.h @@ -0,0 +1,30 @@ +//===--- Opcode.h - Opcodes for the constexpr VM ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines all opcodes executed by the VM and emitted by the compiler. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_OPCODE_H +#define LLVM_CLANG_AST_INTERP_OPCODE_H + +#include + +namespace clang { +namespace interp { + +enum Opcode : uint32_t { +#define GET_OPCODE_NAMES +#include "Opcodes.inc" +#undef GET_OPCODE_NAMES +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Opcodes.td b/clang/lib/AST/Interp/Opcodes.td new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Opcodes.td @@ -0,0 +1,249 @@ +//===--- Opcodes.td - Opcode defitions for the constexpr VM -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Helper file used to generate opcodes, the interpreter and the disassembler. +// +//===----------------------------------------------------------------------===// + + +//===----------------------------------------------------------------------===// +// Types evaluated by the interpreter. +//===----------------------------------------------------------------------===// + +class Type; +def Bool : Type; +def Sint8 : Type; +def Uint8 : Type; +def Sint16 : Type; +def Uint16 : Type; +def Sint32 : Type; +def Uint32 : Type; +def Sint64 : Type; +def Uint64 : Type; +def Ptr : Type; + +//===----------------------------------------------------------------------===// +// Types transferred to the interpreter. +//===----------------------------------------------------------------------===// + +class ArgType { string Name = ?; } +def ArgSint8 : ArgType { let Name = "int8_t"; } +def ArgUint8 : ArgType { let Name = "uint8_t"; } +def ArgSint16 : ArgType { let Name = "int16_t"; } +def ArgUint16 : ArgType { let Name = "uint16_t"; } +def ArgSint32 : ArgType { let Name = "int32_t"; } +def ArgUint32 : ArgType { let Name = "uint32_t"; } +def ArgSint64 : ArgType { let Name = "int64_t"; } +def ArgUint64 : ArgType { let Name = "uint64_t"; } +def ArgBool : ArgType { let Name = "bool"; } +def ArgPtr : ArgType { let Name = "uintptr_t"; } + +//===----------------------------------------------------------------------===// +// Classes of types intructions operate on. +//===----------------------------------------------------------------------===// + +class TypeClass { + list Types; +} + +def AluTypeClass : TypeClass { + let Types = [Sint8, Uint8, Sint16, Uint16, Sint32, + Uint32, Sint64, Uint64, Bool]; +} + +def AllTypeClass : TypeClass { + let Types = !listconcat(AluTypeClass.Types, [Ptr]); +} + +class SingletonTypeClass : TypeClass { + let Types = [Ty]; +} + +//===----------------------------------------------------------------------===// +// Record describing all opcodes. +//===----------------------------------------------------------------------===// + +class Opcode { + list Types = []; + list Args = []; + string Name = ""; + bit CanReturn = 0; + bit ChangesPC = 0; + bit HasCustomLink = 0; + bit HasCustomEval = 0; + bit HasGroup = 0; +} + +class AluOpcode : Opcode { + let Types = [AluTypeClass]; + let HasGroup = 1; +} + +class AluRealOpcode : Opcode { + let Types = [AluTypeClass]; + let HasGroup = 1; +} + +//===----------------------------------------------------------------------===// +// Jump opcodes +//===----------------------------------------------------------------------===// + +class JumpOpcode : Opcode { + let Args = [ArgSint32]; + let ChangesPC = 1; + let HasCustomEval = 1; +} + +def Jmp : JumpOpcode; +def Jt : JumpOpcode; +def Jf : JumpOpcode; + +//===----------------------------------------------------------------------===// +// Returns +//===----------------------------------------------------------------------===// + +def Ret : Opcode { + let Types = [AllTypeClass]; + let ChangesPC = 1; + let CanReturn = 1; + let HasGroup = 1; + let HasCustomEval = 1; +} +def RetVoid : Opcode { + let CanReturn = 1; + let ChangesPC = 1; + let HasCustomEval = 1; +} +def NoRet : Opcode {} + +//===----------------------------------------------------------------------===// +// Frame management +//===----------------------------------------------------------------------===// + +def Destroy : Opcode { + let Args = [ArgUint32]; + let HasCustomEval = 1; +} + +//===----------------------------------------------------------------------===// +// Constants +//===----------------------------------------------------------------------===// + +class ConstOpcode : Opcode { + let Types = [SingletonTypeClass]; + let Args = [ArgTy]; + let Name = "Const"; +} + +def ConstSint8 : ConstOpcode; +def ConstUint8 : ConstOpcode; +def ConstSint16 : ConstOpcode; +def ConstUint16 : ConstOpcode; +def ConstSint32 : ConstOpcode; +def ConstUint32 : ConstOpcode; +def ConstSint64 : ConstOpcode; +def ConstUint64 : ConstOpcode; +def ConstBool : ConstOpcode; + +def Zero : Opcode { + let Types = [AluTypeClass]; +} + +def NullPtr : Opcode; + +//===----------------------------------------------------------------------===// +// Pointer generation +//===----------------------------------------------------------------------===// + +def GetPtrLocal : Opcode { + let Args = [ArgUint32]; + bit HasCustomEval = 1; +} +def GetPtrParam : Opcode { + let Args = [ArgUint32]; +} + +def Undef : Opcode; + +//===----------------------------------------------------------------------===// +// Direct field accessors +//===----------------------------------------------------------------------===// + +class AccessOpcode : Opcode { + let Types = [AllTypeClass]; + let Args = [ArgUint32]; + let HasGroup = 1; +} + +def GetLocal : AccessOpcode { let HasCustomEval = 1; } +def SetLocal : AccessOpcode { let HasCustomEval = 1; } + +def GetParam : AccessOpcode; +def SetParam : AccessOpcode; + +//===----------------------------------------------------------------------===// +// Pointer access +//===----------------------------------------------------------------------===// + +class LoadOpcode : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +def Load : LoadOpcode {} +def LoadPop : LoadOpcode {} + +class StoreOpcode : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +def Store : StoreOpcode {} +def StorePop : StoreOpcode {} + +def Init : StoreOpcode {} + +//===----------------------------------------------------------------------===// +// Binary operators. +//===----------------------------------------------------------------------===// + +def Sub : AluRealOpcode; +def Add : AluRealOpcode; +def Mul : AluRealOpcode; +def Div : AluRealOpcode; +def Rem : AluOpcode; + +//===----------------------------------------------------------------------===// +// Comparison opcodes. +//===----------------------------------------------------------------------===// + +class ComparisonOpcode : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +def EQ : ComparisonOpcode; +def NE : ComparisonOpcode; +def LT : ComparisonOpcode; +def LE : ComparisonOpcode; +def GT : ComparisonOpcode; +def GE : ComparisonOpcode; + +//===----------------------------------------------------------------------===// +// Stack management. +//===----------------------------------------------------------------------===// + +def Pop : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +def Dup : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} diff --git a/clang/lib/AST/Interp/Pointer.h b/clang/lib/AST/Interp/Pointer.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Pointer.h @@ -0,0 +1,267 @@ +//===--- Pointer.h - Types for the constexpr VM -----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the classes responsible for pointer tracking. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_POINTER_H +#define LLVM_CLANG_AST_INTERP_POINTER_H + +#include "Descriptor.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "llvm/ADT/PointerUnion.h" + +namespace clang { +namespace interp { +class Block; +class DeadBlock; +class Context; +class InterpState; +class Pointer; +enum PrimType : unsigned; + +/// A memory block, either on the stack or in the heap. +/// +/// The storage described by the block immediately follows it in memory. +class Block { +public: + // Creates a new block. + Block(Descriptor *Desc, bool IsStatic = false, bool IsExtern = false) + : IsStatic(IsStatic), IsExtern(IsExtern), Desc(Desc) {} + + /// Returns the block's descriptor. + Descriptor *getDescriptor() const { return Desc; } + /// Checks if the block has any live pointers. + bool hasPointers() const { return Pointers; } + /// Checks if the block is extern. + bool isExtern() const { return IsExtern; } + /// Checks if the block has static storage duration. + bool isStatic() const { return IsStatic; } + /// Returns the size of the block. + InterpSize getSize() const { return Desc->Size; } + + /// Returns a pointer to the stored data. + char *data() { return reinterpret_cast(this + 1); } + +protected: + friend class Pointer; + friend class DeadBlock; + friend class InterpState; + + Block(Descriptor *Desc, bool IsExtern, bool IsStatic, bool IsDead) + : IsStatic(IsStatic), IsExtern(IsExtern), IsDead(true), Desc(Desc) {} + + // Deletes a dead block at the end of its lifetime. + void cleanup(); + + // Pointer chain management. + void addPointer(Pointer *P); + void removePointer(Pointer *P); + void movePointer(Pointer *From, Pointer *To); + + /// Start of the chain of pointers. + Pointer *Pointers = nullptr; + /// Flag indicating if the block has static storage duration. + bool IsStatic = false; + /// Flag indicating if the block is an extern. + bool IsExtern = false; + /// Flag indicating if the pointer is dead. + bool IsDead = false; + /// Pointer to the stack slot descriptor. + Descriptor *Desc; +}; + +/// Descriptor for a dead block. +/// +/// Dead blocks are chained in a double-linked list to deallocate them +/// whenever pointers become dead. +class DeadBlock { +public: + /// Copies the block. + DeadBlock(DeadBlock *&Root, Block *Blk); + + /// Returns a pointer to the stored data. + char *data() { return B.data(); } + +private: + friend class Block; + friend class InterpState; + + void free(); + + /// Root pointer of the list. + DeadBlock *&Root; + /// Previous block in the list. + DeadBlock *Prev; + /// Next block in the list. + DeadBlock *Next; + + /// Actual block storing data and tracking pointers. + Block B; +}; + +/// A pointer to a memory block, live or dead. +/// +/// This object can be allocated into interpreter stack frames. If pointing to +/// a live block, it is a link in the chain of pointers pointing to the block. +class Pointer { +public: + Pointer() {} + Pointer(Block *B); + Pointer(const Pointer &P); + Pointer(Pointer &&P); + ~Pointer(); + + void operator=(const Pointer &P); + void operator=(Pointer &&P); + + /// Converts the pointer to an APValue. + llvm::Optional toAPValue() const; + + /// Offsets a pointer inside an array. + Pointer atOffset(unsigned Off) const { + if (getFieldDesc()->ElemDesc) + Off += sizeof(InlineDescriptor); + return Pointer(Pointee, Base, Base + Off); + } + + /// Creates a pointer to a field. + Pointer atField(unsigned Off) const { + unsigned Field = Offset + Off; + return Pointer(Pointee, Field, Field); + } + + /// Narrows a pointer to a field. + Pointer narrow() const { + return Pointer(Pointee, Offset, Offset); + } + + /// Expands a pointer to the container. + Pointer expand() const { + if (Base == 0) + return *this; + return getBase(); + } + + /// Checks if the pointer is null. + bool isNull() const { return Pointee == nullptr; } + /// Checks if the pointer is live. + bool isLive() const { return Pointee && !Pointee->IsDead; } + /// Checks if the pointer is in bounds. + bool inBounds() const { return Offset < Base + size(); } + /// Checks if the item is a field in an object. + bool isField() const { return Base != 0; } + + /// Accessor for information about the declaration site. + Descriptor *getDeclDesc() const { return Pointee->Desc; } + SourceLocation getDeclLoc() const { return getDeclDesc()->getLocation(); } + + /// Returns a pointer to the object of which this pointer is a field. + Pointer getBase() const { + assert(Base != 0 && "Not a nested pointer"); + unsigned NewBase = Base - getInlineDescriptor()->Offset; + Descriptor *Desc; + if (NewBase == 0) { + Desc = Pointee->Desc; + } else { + auto *I = reinterpret_cast(Pointee->data() + NewBase); + Desc = (I - 1)->Desc; + } + unsigned Start = Desc->ElemDesc ? sizeof(InlineDescriptor) : 0; + return Pointer(Pointee, NewBase, NewBase + Start); + } + + /// Accessors for information about the innermost field. + Descriptor *getFieldDesc() const { + if (Base == 0) + return getDeclDesc(); + return getInlineDescriptor()->Desc; + } + + /// Returns the type of the innermost field. + QualType getType() const { return getFieldDesc()->getType(); } + /// Returns the element size of the innermost field. + size_t elemSize() const { return getFieldDesc()->ElemSize; } + /// Returns the total size of the innermost field. + size_t size() const { return getFieldDesc()->Size; } + /// Checks if the innermost field is an array. + bool isArray() const { return getFieldDesc()->IsArray; } + /// Checks if the storage is extern. + bool isExtern() const { return Pointee->isExtern(); } + + /// Checks if an object or a subfield is mutable. + bool isMutable() const { + if (Base == 0) + return getDeclDesc()->IsMutable; + return getInlineDescriptor()->IsMutable; + } + + /// Checks if an object was initialized. + bool isInitialized() const { + if (Base == 0) + return true; + return getInlineDescriptor()->IsInitialized; + } + + /// Returns the offset into an array. + unsigned getOffset() const { + if (Offset > Base && getFieldDesc()->ElemDesc) + return Offset - Base - sizeof(InlineDescriptor); + return Offset - Base; + } + /// Returns the index into an array. + int64_t getIndex() const { return getOffset() / elemSize(); } + /// Checks if the declaration is a temporary. + bool isTemporary() const { return getDeclDesc()->IsTemporary; } + + /// Dereferences the pointer, if it's live. + template T &deref() const { + assert(isLive() && "Invalid pointer"); + return *reinterpret_cast(Pointee->data() + Offset); + } + + /// Initializes a field. + void initialize() const { + assert(Base != 0 && "Only fields can be initialised"); + getInlineDescriptor()->IsInitialized = true; + } + + /// Checks if two pointers are comparable. + static bool isComparable(const Pointer &A, const Pointer &B); + +private: + friend class Block; + friend class DeadBlock; + + Pointer(Block *Pointee, unsigned Base, unsigned Offset); + + /// Returns the embedded descriptor preceding a field. + InlineDescriptor *getInlineDescriptor() const { + assert(Base != 0 && "Not a nested pointer"); + return reinterpret_cast(Pointee->data() + Base) - 1; + } + + /// The block the pointer is pointing to. + Block *Pointee = nullptr; + /// Start of the current subfield. + unsigned Base = 0; + /// Offset into the block. + unsigned Offset = 0; + + /// Previous link in the pointer chain. + Pointer *Prev = nullptr; + /// Next link in the pointer chain. + Pointer *Next = nullptr; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Pointer.cpp b/clang/lib/AST/Interp/Pointer.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Pointer.cpp @@ -0,0 +1,169 @@ +//===--- Pointer.cpp - Types for the constexpr VM ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Pointer.h" +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +void Block::addPointer(Pointer *P) { + if (IsStatic) + return; + if (Pointers) { + Pointers->Prev = P; + } + P->Next = Pointers; + P->Prev = nullptr; + Pointers = P; +} + +void Block::removePointer(Pointer *P) { + if (IsStatic) + return; + if (Pointers == P) + Pointers = P->Next; + if (P->Prev) + P->Prev->Next = P->Next; + if (P->Next) + P->Next->Prev = P->Prev; +} + +void Block::cleanup() { + if (Pointers == nullptr && IsDead) + (reinterpret_cast(this + 1) - 1)->free(); +} + +void Block::movePointer(Pointer *From, Pointer *To) { + if (IsStatic) + return; + To->Prev = From->Prev; + if (To->Prev) + To->Prev->Next = To; + To->Next = From->Next; + if (To->Next) + To->Next->Prev = To; + if (Pointers == From) + Pointers = To; + + From->Prev = nullptr; + From->Next = nullptr; +} + +DeadBlock::DeadBlock(DeadBlock *&Root, Block *Blk) + : Root(Root), B(Blk->Desc, Blk->IsStatic, Blk->IsExtern, /*isDead=*/true) { + // Add the block to the chain of dead blocks. + if (Root) + Root->Prev = this; + + Next = Root; + Prev = nullptr; + Root = this; + + // Transfer pointers. + B.Pointers = Blk->Pointers; + for (Pointer *P = Blk->Pointers; P; P = P->Next) + P->Pointee = &B; +} + +void DeadBlock::free() { + if (Prev) + Prev->Next = Next; + if (Next) + Next->Prev = Prev; + if (Root == this) + Root = Next; + ::free(this); +} + +Pointer::Pointer(Block *Pointee) : Pointer(Pointee, 0, 0) {} + +Pointer::Pointer(const Pointer &P) : Pointer(P.Pointee, P.Base, P.Offset) {} + +Pointer::Pointer(Pointer &&P) + : Pointee(P.Pointee), Base(P.Base), Offset(P.Offset) { + if (Pointee) + Pointee->movePointer(&P, this); +} + +Pointer::Pointer(Block *Pointee, unsigned Base, unsigned Offset) + : Pointee(Pointee), Base(Base), Offset(Offset) { + assert(Base % alignof(void *) == 0 && "Invalid alignment"); + if (Pointee) + Pointee->addPointer(this); +} + +Pointer::~Pointer() { + if (Pointee) { + Pointee->removePointer(this); + Pointee->cleanup(); + } +} + +void Pointer::operator=(const Pointer &P) { + Block *Old = Pointee; + + if (Pointee) + Pointee->removePointer(this); + + Offset = P.Offset; + Base = P.Base; + + Pointee = P.Pointee; + if (Pointee) + Pointee->addPointer(this); + + if (Old) + Old->cleanup(); +} + +void Pointer::operator=(Pointer &&P) { + Block *Old = Pointee; + + if (Pointee) + Pointee->removePointer(this); + + Offset = P.Offset; + Base = P.Base; + + Pointee = P.Pointee; + if (Pointee) + Pointee->movePointer(&P, this); + + if (Old) + Old->cleanup(); +} + +llvm::Optional Pointer::toAPValue() const { + if (isNull()) + return {}; + + // Build the lvalue base from the block. + Descriptor *Desc = getDeclDesc(); + APValue::LValueBase Base; + if (auto *VD = Desc->Source.dyn_cast()) + Base = VD; + else if (auto *E = Desc->Source.dyn_cast()) + Base = E; + else + llvm_unreachable("Invalid descriptor type"); + + // TODO: compute the offset into the object. + CharUnits Offset = CharUnits::Zero(); + + if (!isField()) { + return APValue(Base, Offset, APValue::NoLValuePath()); + } + + // TODO: return subobject paths. + return {}; +} + +bool Pointer::isComparable(const Pointer &A, const Pointer &B) { + return A.Pointee == B.Pointee; +} diff --git a/clang/lib/AST/Interp/Program.h b/clang/lib/AST/Interp/Program.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Program.h @@ -0,0 +1,99 @@ +//===--- Program.h - Bytecode for the constexpr VM --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines a program which organises and links multiple bytecode functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_PROGRAM_H +#define LLVM_CLANG_AST_INTERP_PROGRAM_H + +#include "Function.h" +#include "Pointer.h" +#include "Source.h" +#include "Type.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Allocator.h" +#include +#include + +namespace clang { +class RecordDecl; +class Expr; +class FunctionDecl; +class Stmt; +class StringLiteral; +class VarDecl; + +namespace interp { +class Context; +class Scope; + +/// The program contains and links the bytecode for all functions. +class Program { +public: + Program(Context &Ctx) : Ctx(Ctx) {} + + /// Creates a new function from a code range. + template + Function *createFunction(const FunctionDecl *Def, Ts &&... Args) { + auto *Func = new Function(*this, Def, std::forward(Args)...); + Funcs.insert({Def, std::unique_ptr(Func)}); + return Func; + } + + /// Creates an anonymous function. + template + Function *createFunction(Ts &&... Args) { + auto *Func = new Function(*this, std::forward(Args)...); + AnonFuncs.emplace_back(Func); + return Func; + } + + /// Returns a function. + Function *getFunction(const FunctionDecl *F); + + /// Creates a descriptor for a primitive type. + Descriptor *createDescriptor(const DeclTy &D, PrimType Type, + bool IsMutable = true, + bool IsTemporary = false) { + return allocateDescriptor(std::move(D), Type, IsMutable, IsTemporary); + } + +private: + /// Reference to the VM context. + Context &Ctx; + /// Mapping from decls to cached bytecode functions. + llvm::DenseMap> Funcs; + /// List of anonymous functions. + std::vector> AnonFuncs; + + /// Custom allocator for global storage. + using PoolAllocTy = llvm::BumpPtrAllocatorImpl; + + /// Allocator for globals and descriptors. + PoolAllocTy Allocator; + + /// Creates a new descriptor. + template + Descriptor *allocateDescriptor(Ts &&... Args) { + return new (Allocator) Descriptor(std::forward(Args)...); + } + +public: + /// Dumps the disassembled bytecode to \c llvm::errs(). + void dump() const; + void dump(llvm::raw_ostream &OS) const; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Program.cpp b/clang/lib/AST/Interp/Program.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Program.cpp @@ -0,0 +1,24 @@ +//===--- Program.cpp - Bytecode for the constexpr VM ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Program.h" +#include "Context.h" +#include "Function.h" +#include "Opcode.h" +#include "Type.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +Function *Program::getFunction(const FunctionDecl *F) { + F = F->getDefinition(); + auto It = Funcs.find(F); + return It == Funcs.end() ? nullptr : It->second.get(); +} diff --git a/clang/lib/AST/Interp/Source.h b/clang/lib/AST/Interp/Source.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Source.h @@ -0,0 +1,103 @@ +//===--- Source.h - Source location provider for the VM --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines a program which organises and links multiple bytecode functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_SOURCE_H +#define LLVM_CLANG_AST_INTERP_SOURCE_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "llvm/Support/Endian.h" + +namespace clang { +namespace interp { +class Function; + +/// Pointer into the code segment. +class CodePtr { +public: + CodePtr() : Ptr(nullptr) {} + + CodePtr &operator+=(int32_t Offset) { + Ptr += Offset; + return *this; + } + + int32_t operator-(const CodePtr &RHS) const { + assert(Ptr != nullptr && RHS.Ptr != nullptr && "Invalid code pointer"); + return Ptr - RHS.Ptr; + } + + CodePtr operator-(size_t RHS) const { + assert(Ptr != nullptr && "Invalid code pointer"); + return CodePtr(Ptr - RHS); + } + + bool operator!=(const CodePtr &RHS) const { return Ptr != RHS.Ptr; } + + /// Reads data and advances the pointer. + template T read() { + using namespace llvm::support; + T Value = endian::read(Ptr); + Ptr += sizeof(T); + return Value; + } + +private: + /// Constructor used by Function to generate pointers. + CodePtr(const char *Ptr) : Ptr(Ptr) {} + +private: + friend class Function; + + /// Pointer into the code owned by a function. + const char *Ptr; +}; + +/// Describes the statement/declaration an opcode was generated from. +class SourceInfo { +public: + SourceInfo() {} + SourceInfo(const Stmt *E) : Source(E) {} + SourceInfo(const VarDecl *D) : Source(D) {} + + SourceLocation getLoc() const; + + const Stmt *asStmt() const { return Source.dyn_cast(); } + const VarDecl *asDecl() const { return Source.dyn_cast(); } + const Expr *asExpr() const; + + operator bool() const { return !Source.isNull(); } + +private: + llvm::PointerUnion Source; +}; + +using SourceMap = std::vector>; + +/// Interface for classes which map locations to sources. +class SourceMapper { +public: + virtual ~SourceMapper() {} + + /// Returns source information for a given PC in a function. + virtual SourceInfo getSource(Function *F, CodePtr PC) const = 0; + + /// Returns the expression if an opcode belongs to one, null otherwise. + const Expr *getExpr(Function *F, CodePtr PC) const; + /// Returns the location from which an opcode originates. + SourceLocation getLocation(Function *F, CodePtr PC) const; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Source.cpp b/clang/lib/AST/Interp/Source.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Source.cpp @@ -0,0 +1,39 @@ +//===--- Source.cpp - Source expression tracking ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Source.h" +#include "clang/AST/Expr.h" + +using namespace clang; +using namespace clang::interp; + +SourceLocation SourceInfo::getLoc() const { + if (auto *E = asExpr()) + return E->getExprLoc(); + if (auto *S = asStmt()) + return S->getBeginLoc(); + if (auto *D = asDecl()) + return D->getBeginLoc(); + return SourceLocation(); +} + +const Expr *SourceInfo::asExpr() const { + if (auto *S = Source.dyn_cast()) + return dyn_cast(S); + return nullptr; +} + +const Expr *SourceMapper::getExpr(Function *F, CodePtr PC) const { + if (auto *E = getSource(F, PC).asExpr()) + return E; + llvm::report_fatal_error("missing source expression"); +} + +SourceLocation SourceMapper::getLocation(Function *F, CodePtr PC) const { + return getSource(F, PC).getLoc(); +} diff --git a/clang/lib/AST/Interp/State.h b/clang/lib/AST/Interp/State.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/State.h @@ -0,0 +1,129 @@ +//===--- State.h - State chain for the VM and AST Walker --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the base class of the interpreter and evaluator state. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_STATE_H +#define LLVM_CLANG_AST_INTERP_STATE_H + +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/Expr.h" +#include "clang/Basic/OptionalDiagnostic.h" + +namespace clang { + +/// Kinds of access we can perform on an object, for diagnostics. Note that +/// we consider a member function call to be a kind of access, even though +/// it is not formally an access of the object, because it has (largely) the +/// same set of semantic restrictions. +enum AccessKinds { + AK_Read, + AK_Assign, + AK_Increment, + AK_Decrement, + AK_MemberCall, + AK_DynamicCast, + AK_TypeId, +}; + +// The order of this enum is important for diagnostics. +enum CheckSubobjectKind { + CSK_Base, + CSK_Derived, + CSK_Field, + CSK_ArrayToPointer, + CSK_ArrayIndex, + CSK_Real, + CSK_Imag +}; + +namespace interp { +class Frame; +class SourceInfo; + +/// Interface for the VM to interact with the AST walker's context. +class State { +public: + virtual ~State(); + + virtual bool checkingForOverflow() const = 0; + virtual bool checkingPotentialConstantExpression() const = 0; + virtual bool noteUndefinedBehavior() = 0; + virtual Frame *getCurrentFrame() = 0; + virtual const Frame *getBottomFrame() const = 0; + virtual bool hasActiveDiagnostic() = 0; + virtual void setActiveDiagnostic(bool Flag) = 0; + virtual void setFoldFailureDiagnostic(bool Flag) = 0; + virtual Expr::EvalStatus &getEvalStatus() const = 0; + virtual ASTContext &getCtx() const = 0; + virtual bool hasPriorDiagnostic() = 0; + virtual unsigned getCallStackDepth() = 0; + +public: + // Diagnose that the evaluation could not be folded (FF => FoldFailure) + OptionalDiagnostic + FFDiag(SourceLocation Loc, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + FFDiag(const Expr *E, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + FFDiag(const SourceInfo &SI, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + /// Diagnose that the evaluation does not produce a C++11 core constant + /// expression. + /// + /// FIXME: Stop evaluating if we're in EM_ConstantExpression or + /// EM_PotentialConstantExpression mode and we produce one of these. + OptionalDiagnostic + CCEDiag(SourceLocation Loc, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + CCEDiag(const Expr *E, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + CCEDiag(const SourceInfo &SI, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + /// Add a note to a prior diagnostic. + OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId); + + /// Add a stack of notes to a prior diagnostic. + void addNotes(ArrayRef Diags); + + /// Directly reports a diagnostic message. + DiagnosticBuilder report(SourceLocation Loc, diag::kind DiagId); + + const LangOptions &getLangOpts() const; + +private: + void addCallStack(unsigned Limit); + + PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId); + + OptionalDiagnostic diag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes, bool IsCCEDiag); +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/State.cpp b/clang/lib/AST/Interp/State.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/State.cpp @@ -0,0 +1,158 @@ +//===--- State.cpp - State chain for the VM and AST Walker ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "State.h" +#include "Frame.h" +#include "Program.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/CXXInheritance.h" + +using namespace clang; +using namespace clang::interp; + +State::~State() {} + +OptionalDiagnostic State::FFDiag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes) { + return diag(Loc, DiagId, ExtraNotes, false); +} + +OptionalDiagnostic State::FFDiag(const Expr *E, diag::kind DiagId, + unsigned ExtraNotes) { + if (getEvalStatus().Diag) + return diag(E->getExprLoc(), DiagId, ExtraNotes, false); + setActiveDiagnostic(false); + return OptionalDiagnostic(); +} + +OptionalDiagnostic State::FFDiag(const SourceInfo &SI, diag::kind DiagId, + unsigned ExtraNotes) { + if (getEvalStatus().Diag) + return diag(SI.getLoc(), DiagId, ExtraNotes, false); + setActiveDiagnostic(false); + return OptionalDiagnostic(); +} + +OptionalDiagnostic State::CCEDiag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes) { + // Don't override a previous diagnostic. Don't bother collecting + // diagnostics if we're evaluating for overflow. + if (!getEvalStatus().Diag || !getEvalStatus().Diag->empty()) { + setActiveDiagnostic(false); + return OptionalDiagnostic(); + } + return diag(Loc, DiagId, ExtraNotes, true); +} + +OptionalDiagnostic State::CCEDiag(const Expr *E, diag::kind DiagId, + unsigned ExtraNotes) { + return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes); +} + +OptionalDiagnostic State::CCEDiag(const SourceInfo &SI, diag::kind DiagId, + unsigned ExtraNotes) { + return CCEDiag(SI.getLoc(), DiagId, ExtraNotes); +} + +OptionalDiagnostic State::Note(SourceLocation Loc, diag::kind DiagId) { + if (!hasActiveDiagnostic()) + return OptionalDiagnostic(); + return OptionalDiagnostic(&addDiag(Loc, DiagId)); +} + +void State::addNotes(ArrayRef Diags) { + if (hasActiveDiagnostic()) { + getEvalStatus().Diag->insert(getEvalStatus().Diag->end(), Diags.begin(), + Diags.end()); + } +} + +DiagnosticBuilder State::report(SourceLocation Loc, diag::kind DiagId) { + return getCtx().getDiagnostics().Report(Loc, DiagId); +} + +/// Add a diagnostic to the diagnostics list. +PartialDiagnostic &State::addDiag(SourceLocation Loc, diag::kind DiagId) { + PartialDiagnostic PD(DiagId, getCtx().getDiagAllocator()); + getEvalStatus().Diag->push_back(std::make_pair(Loc, PD)); + return getEvalStatus().Diag->back().second; +} + +OptionalDiagnostic State::diag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes, bool IsCCEDiag) { + auto &EvalStatus = getEvalStatus(); + if (EvalStatus.Diag) { + if (hasPriorDiagnostic()) { + return OptionalDiagnostic(); + } + + unsigned CallStackNotes = getCallStackDepth() - 1; + unsigned Limit = getCtx().getDiagnostics().getConstexprBacktraceLimit(); + if (Limit) + CallStackNotes = std::min(CallStackNotes, Limit + 1); + if (checkingPotentialConstantExpression()) + CallStackNotes = 0; + + setActiveDiagnostic(true); + setFoldFailureDiagnostic(!IsCCEDiag); + EvalStatus.Diag->clear(); + EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes); + addDiag(Loc, DiagId); + if (!checkingPotentialConstantExpression()) { + addCallStack(Limit); + } + return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second); + } + setActiveDiagnostic(false); + return OptionalDiagnostic(); +} + +const LangOptions &State::getLangOpts() const { return getCtx().getLangOpts(); } + +void State::addCallStack(unsigned Limit) { + // Determine which calls to skip, if any. + unsigned ActiveCalls = getCallStackDepth() - 1; + unsigned SkipStart = ActiveCalls, SkipEnd = SkipStart; + if (Limit && Limit < ActiveCalls) { + SkipStart = Limit / 2 + Limit % 2; + SkipEnd = ActiveCalls - Limit / 2; + } + + // Walk the call stack and add the diagnostics. + unsigned CallIdx = 0; + auto *CurrentCall = getCurrentFrame(); + auto *BottomFrame = getBottomFrame(); + for (auto *F = CurrentCall; F != BottomFrame; F = F->getCaller(), ++CallIdx) { + auto CallLocation = F->getCallLocation(); + + // Skip this call? + if (CallIdx >= SkipStart && CallIdx < SkipEnd) { + if (CallIdx == SkipStart) { + // Note that we're skipping calls. + addDiag(CallLocation, diag::note_constexpr_calls_suppressed) + << unsigned(ActiveCalls - Limit); + } + continue; + } + + // Use a different note for an inheriting constructor, because from the + // user's perspective it's not really a function at all. + if (auto *CD = dyn_cast_or_null(F->getCallee())) { + if (CD->isInheritingConstructor()) { + addDiag(CallLocation, diag::note_constexpr_inherited_ctor_call_here) + << CD->getParent(); + continue; + } + } + + SmallVector Buffer; + llvm::raw_svector_ostream Out(Buffer); + F->describe(Out); + addDiag(CallLocation, diag::note_constexpr_call_here) << Out.str(); + } +} diff --git a/clang/lib/AST/Interp/Type.h b/clang/lib/AST/Interp/Type.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Type.h @@ -0,0 +1,78 @@ +//===--- Type.h - Types for the constexpr VM --------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the VM types and helpers operating on types. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_TYPE_H +#define LLVM_CLANG_AST_INTERP_TYPE_H + +#include "Integral.h" +#include "Pointer.h" +#include +#include +#include + +namespace clang { +namespace interp { + +/// Enumeration of the primitive types of the VM. +enum PrimType : unsigned { + PT_Sint8, + PT_Uint8, + PT_Sint16, + PT_Uint16, + PT_Sint32, + PT_Uint32, + PT_Sint64, + PT_Uint64, + PT_Ptr, + PT_Bool, +}; + +/// Mapping from primitive types to their representation. +template struct PrimConv; +template <> struct PrimConv { using T = Integral<8, true>; }; +template <> struct PrimConv { using T = Integral<8, false>; }; +template <> struct PrimConv { using T = Integral<16, true>; }; +template <> struct PrimConv { using T = Integral<16, false>; }; +template <> struct PrimConv { using T = Integral<32, true>; }; +template <> struct PrimConv { using T = Integral<32, false>; }; +template <> struct PrimConv { using T = Integral<64, true>; }; +template <> struct PrimConv { using T = Integral<64, false>; }; +template <> struct PrimConv { using T = Integral<1, false>; }; +template <> struct PrimConv { using T = Pointer; }; + +/// Returns the size of a primitive type in bytes. +size_t primSize(PrimType Type); + +/// Aligns a size to the pointer alignment. +constexpr size_t align(size_t Size) { + return ((Size + alignof(void *) - 1) / alignof(void *)) * alignof(void *); +} + +} // namespace interp +} // namespace clang + +/// Helper macro to simplify type switches. +/// The macro implicitly exposes a type T in the scope of the inner block. +#define TYPE_SWITCH(Expr, B) \ + switch (Expr) { \ + case PT_Sint8: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Uint8: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Sint16: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Uint16: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Sint32: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Uint32: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Sint64: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Uint64: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Bool: {using T = PrimConv::T; do{B;}while(0); break; } \ + case PT_Ptr: {using T = PrimConv::T; do{B;}while(0); break; } \ + } +#endif diff --git a/clang/lib/AST/Interp/Type.cpp b/clang/lib/AST/Interp/Type.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Type.cpp @@ -0,0 +1,22 @@ +//===--- Type.cpp - Types for the constexpr VM ------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +namespace clang { +namespace interp { + +size_t primSize(PrimType Type) { + TYPE_SWITCH(Type, return sizeof(T)); +} + +} // namespace interp +} // namespace clang diff --git a/clang/lib/Driver/ToolChains/Clang.cpp b/clang/lib/Driver/ToolChains/Clang.cpp --- a/clang/lib/Driver/ToolChains/Clang.cpp +++ b/clang/lib/Driver/ToolChains/Clang.cpp @@ -4429,6 +4429,12 @@ CmdArgs.push_back(A->getValue()); } + if (Args.hasArg(options::OPT_fexperimental_clang_interpreter)) + CmdArgs.push_back("-fexperimental-clang-interpreter"); + + if (Args.hasArg(options::OPT_fforce_experimental_clang_interpreter)) + CmdArgs.push_back("-fforce-experimental-clang-interpreter"); + if (Arg *A = Args.getLastArg(options::OPT_fbracket_depth_EQ)) { CmdArgs.push_back("-fbracket-depth"); CmdArgs.push_back(A->getValue()); diff --git a/clang/lib/Frontend/CompilerInvocation.cpp b/clang/lib/Frontend/CompilerInvocation.cpp --- a/clang/lib/Frontend/CompilerInvocation.cpp +++ b/clang/lib/Frontend/CompilerInvocation.cpp @@ -2752,6 +2752,10 @@ getLastArgIntValue(Args, OPT_fconstexpr_depth, 512, Diags); Opts.ConstexprStepLimit = getLastArgIntValue(Args, OPT_fconstexpr_steps, 1048576, Diags); + Opts.EnableClangInterp = + Args.hasArg(OPT_fexperimental_clang_interpreter); + Opts.ForceClangInterp = + Args.hasArg(OPT_fforce_experimental_clang_interpreter); Opts.BracketDepth = getLastArgIntValue(Args, OPT_fbracket_depth, 256, Diags); Opts.DelayedTemplateParsing = Args.hasArg(OPT_fdelayed_template_parsing); Opts.NumLargeByValueCopy = diff --git a/clang/test/AST/Interp/cond.cpp b/clang/test/AST/Interp/cond.cpp new file mode 100644 --- /dev/null +++ b/clang/test/AST/Interp/cond.cpp @@ -0,0 +1,11 @@ +// RUN: %clang_cc1 -std=c++17 -fsyntax-only -fforce-experimental-clang-interpreter %s -verify +// RUN: %clang_cc1 -std=c++17 -fsyntax-only %s -verify +// expected-no-diagnostics + +constexpr int cond_then_else(int a, int b) { + if (a < b) { + return b - a; + } else { + return a - b; + } +} diff --git a/clang/utils/TableGen/CMakeLists.txt b/clang/utils/TableGen/CMakeLists.txt --- a/clang/utils/TableGen/CMakeLists.txt +++ b/clang/utils/TableGen/CMakeLists.txt @@ -8,6 +8,7 @@ ClangCommentHTMLTagsEmitter.cpp ClangDataCollectorsEmitter.cpp ClangDiagnosticsEmitter.cpp + ClangOpcodesEmitter.cpp ClangOpenCLBuiltinEmitter.cpp ClangOptionDocEmitter.cpp ClangSACheckersEmitter.cpp diff --git a/clang/utils/TableGen/ClangOpcodesEmitter.cpp b/clang/utils/TableGen/ClangOpcodesEmitter.cpp new file mode 100644 --- /dev/null +++ b/clang/utils/TableGen/ClangOpcodesEmitter.cpp @@ -0,0 +1,356 @@ +//=== ClangOpcodesEmitter.cpp - constexpr interpreter opcodes ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// These tablegen backends emit Clang AST node tables +// +//===----------------------------------------------------------------------===// + +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" +#include "llvm/TableGen/StringMatcher.h" +#include "llvm/TableGen/TableGenBackend.h" + +using namespace llvm; + +namespace { +class ClangOpcodesEmitter { + RecordKeeper &Records; + Record Root; + unsigned NumTypes; + +public: + ClangOpcodesEmitter(RecordKeeper &R) + : Records(R), Root("Opcode", SMLoc(), R), + NumTypes(Records.getAllDerivedDefinitions("Type").size()) {} + + void run(raw_ostream &OS); + +private: + /// Emits the opcode name for the opcode enum. + /// The name is obtained by concatenating the name with the list of types. + void EmitEnum(raw_ostream &OS, StringRef N, Record *R); + + /// Emits the switch case and the invocation in the interpreter. + void EmitInterp(raw_ostream &OS, StringRef N, Record *R); + + /// Emits the disassembler. + void EmitDisasm(raw_ostream &OS, StringRef N, Record *R); + + /// Emits the LinkEmitter method. + void EmitLink(raw_ostream &OS, StringRef N, Record *R); + + /// Emits the prototype. + void EmitProto(raw_ostream &OS, StringRef N, Record *R); + + /// Emits the prototype to dispatch from a type. + void EmitGroup(raw_ostream &OS, StringRef N, Record *R); + + /// Emits the evaluator method. + void EmitEval(raw_ostream &OS, StringRef N, Record *R); + + void PrintTypes(raw_ostream &OS, ArrayRef Types); +}; + +void Enumerate(const Record *R, + StringRef N, + std::function, Twine)> &&F) { + llvm::SmallVector TypePath; + auto *Types = R->getValueAsListInit("Types"); + + std::function Rec; + Rec = [&TypePath, Types, &Rec, &F](size_t I, const Twine &ID) { + if (I >= Types->size()) { + F(TypePath, ID); + return; + } + + if (auto *TypeClass = dyn_cast(Types->getElement(I))) { + for (auto *Type : TypeClass->getDef()->getValueAsListOfDefs("Types")) { + TypePath.push_back(Type); + Rec(I + 1, ID + Type->getName()); + TypePath.pop_back(); + } + } else { + PrintFatalError("Expected a type class"); + } + }; + Rec(0, N); +} + +} // namespace + +void ClangOpcodesEmitter::run(raw_ostream &OS) { + for (auto *Opcode : Records.getAllDerivedDefinitions(Root.getName())) { + // The name is the record name, unless overriden. + StringRef N = Opcode->getValueAsString("Name"); + if (N.empty()) + N = Opcode->getName(); + + EmitEnum(OS, N, Opcode); + EmitInterp(OS, N, Opcode); + EmitDisasm(OS, N, Opcode); + EmitProto(OS, N, Opcode); + EmitGroup(OS, N, Opcode); + EmitLink(OS, N, Opcode); + EmitEval(OS, N, Opcode); + } +} + +void ClangOpcodesEmitter::EmitEnum(raw_ostream &OS, StringRef N, Record *R) { + OS << "#ifdef GET_OPCODE_NAMES\n"; + Enumerate(R, N, [&OS](ArrayRef, const Twine &ID) { + OS << "OP_" << ID << ",\n"; + }); + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::EmitInterp(raw_ostream &OS, StringRef N, Record *R) { + OS << "#ifdef GET_INTERP\n"; + + Enumerate(R, N, [this, R, &OS, &N](ArrayRef TS, const Twine &ID) { + bool CanReturn = R->getValueAsBit("CanReturn"); + bool ChangesPC = R->getValueAsBit("ChangesPC"); + auto Args = R->getValueAsListOfDefs("Args"); + + OS << "case OP_" << ID << ": {\n"; + + // Emit calls to read arguments. + for (size_t I = 0, N = Args.size(); I < N; ++I) { + OS << "\tauto V" << I; + OS << " = "; + OS << "PC.read<" << Args[I]->getValueAsString("Name") << ">();\n"; + } + + // Emit a call to the template method and pass arguments. + OS << "\tif (!" << N; + PrintTypes(OS, TS); + OS << "(S"; + if (ChangesPC) + OS << ", PC"; + else + OS << ", OpPC"; + if (CanReturn) + OS << ", Result"; + for (size_t I = 0, N = Args.size(); I < N; ++I) + OS << ", V" << I; + OS << "))\n"; + OS << "\t\treturn false;\n"; + + // Bail out if interpreter returned. + if (CanReturn) { + OS << "\tif (!S.Current || S.Current->isRoot())\n"; + OS << "\t\treturn true;\n"; + } + + OS << "\tcontinue;\n"; + OS << "}\n"; + }); + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::EmitDisasm(raw_ostream &OS, StringRef N, Record *R) { + OS << "#ifdef GET_DISASM\n"; + Enumerate(R, N, [R, &OS](ArrayRef, const Twine &ID) { + OS << "case OP_" << ID << ":\n"; + OS << "\tPrintName(\"" << ID << "\");\n"; + OS << "\tOS << \"\\t\""; + + for (auto *Arg : R->getValueAsListOfDefs("Args")) + OS << " << PC.read<" << Arg->getValueAsString("Name") << ">() << \" \""; + + OS << "<< \"\\n\";\n"; + OS << "\tcontinue;\n"; + }); + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::EmitLink(raw_ostream &OS, StringRef N, Record *R) { + if (R->getValueAsBit("HasCustomLink")) + return; + + OS << "#ifdef GET_LINK_IMPL\n"; + Enumerate(R, N, [R, &OS](ArrayRef, const Twine &ID) { + auto Args = R->getValueAsListOfDefs("Args"); + + // Emit the list of arguments. + OS << "bool LinkEmitter::emit" << ID << "("; + for (size_t I = 0, N = Args.size(); I < N; ++I) + OS << "const " << Args[I]->getValueAsString("Name") << " &A" << I << ","; + OS << "const SourceInfo &L) {\n"; + + // Emit a call to write the opcodes. + OS << "\treturn emitOp<"; + for (size_t I = 0, N = Args.size(); I < N; ++I) { + if (I != 0) + OS << ", "; + OS << Args[I]->getValueAsString("Name"); + } + OS << ">(OP_" << ID; + for (size_t I = 0, N = Args.size(); I < N; ++I) + OS << ", A" << I; + OS << ", L);\n"; + OS << "}\n"; + }); + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::EmitProto(raw_ostream &OS, StringRef N, Record *R) { + OS << "#if defined(GET_EVAL_PROTO) || defined(GET_LINK_PROTO)\n"; + auto Args = R->getValueAsListOfDefs("Args"); + Enumerate(R, N, [&OS, &Args](ArrayRef TS, const Twine &ID) { + OS << "bool emit" << ID << "("; + for (auto *Arg : Args) + OS << "const " << Arg->getValueAsString("Name") << " &, "; + OS << "const SourceInfo &);\n"; + }); + + // Emit a template method for custom emitters to have less to implement. + auto TypeCount = R->getValueAsListInit("Types")->size(); + if (R->getValueAsBit("HasCustomEval") && TypeCount) { + OS << "#if defined(GET_EVAL_PROTO)\n"; + OS << "template<"; + for (size_t I = 0; I < TypeCount; ++I) { + if (I != 0) + OS << ", "; + OS << "PrimType"; + } + OS << ">\n"; + OS << "bool emit" << N << "("; + for (auto *Arg : Args) + OS << "const " << Arg->getValueAsString("Name") << " &,"; + OS << "const SourceInfo &);\n"; + OS << "#endif\n"; + } + + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::EmitGroup(raw_ostream &OS, StringRef N, Record *R) { + if (!R->getValueAsBit("HasGroup")) + return; + + auto *Types = R->getValueAsListInit("Types"); + auto Args = R->getValueAsListOfDefs("Args"); + + // Emit the prototype of the group emitter in the header. + OS << "#if defined(GET_EVAL_PROTO) || defined(GET_LINK_PROTO)\n"; + OS << "bool emit" << N << "("; + for (size_t I = 0, N = Types->size(); I < N; ++I) + OS << "PrimType, "; + for (auto *Arg : Args) + OS << "const " << Arg->getValueAsString("Name") << " &, "; + OS << "const SourceInfo &I);\n"; + OS << "#endif\n"; + + // Emit the dispatch implementation in the source. + OS << "#if defined(GET_EVAL_IMPL) || defined(GET_LINK_IMPL)\n"; + OS << "bool \n"; + OS << "#if defined(GET_EVAL_IMPL)\nEvalEmitter\n#else\nLinkEmitter\n#endif\n"; + OS << "::emit" << N << "("; + for (size_t I = 0, N = Types->size(); I < N; ++I) + OS << "PrimType T" << I << ", "; + for (size_t I = 0, N = Args.size(); I < N; ++I) + OS << "const " << Args[I]->getValueAsString("Name") << " &A" << I << ", "; + OS << "const SourceInfo &I) {\n"; + + std::function Rec; + llvm::SmallVector TS; + Rec = [this, &Rec, &OS, Types, &Args, R, &TS, N](size_t I, const Twine &ID) { + if (I >= Types->size()) { + // Print a call to the emitter method. + // Custom evaluator methods dispatch to template methods. + if (R->getValueAsBit("HasCustomEval")) { + OS << "#ifdef GET_LINK_IMPL\n"; + OS << "return emit" << ID << "\n"; + OS << "#else\n"; + OS << "return emit" << N; + PrintTypes(OS, TS); + OS << "\n#endif\n"; + } else { + OS << "return emit" << ID; + } + + OS << "("; + for (size_t I = 0; I < Args.size(); ++I) { + OS << "A" << I << ", "; + } + OS << "I);\n"; + return; + } + + // Print a switch statement selecting T. + if (auto *TypeClass = dyn_cast(Types->getElement(I))) { + OS << "switch (T" << I << "){\n"; + auto Cases = TypeClass->getDef()->getValueAsListOfDefs("Types"); + for (auto *Case : Cases) { + OS << "case PT_" << Case->getName() << ":\n"; + TS.push_back(Case); + Rec(I + 1, ID + Case->getName()); + TS.pop_back(); + } + // Emit a default case if not all types are present. + if (Cases.size() < NumTypes) { + OS << "default: llvm_unreachable(\"invalid\");\n"; + } + OS << "}\n"; + } else { + PrintFatalError("Expected a type class"); + } + }; + Rec(0, N); + + OS << "}\n"; + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::EmitEval(raw_ostream &OS, StringRef N, Record *R) { + if (R->getValueAsBit("HasCustomEval")) + return; + + OS << "#ifdef GET_EVAL_IMPL\n"; + Enumerate(R, N, [this, R, &N, &OS](ArrayRef TS, const Twine &ID) { + auto Args = R->getValueAsListOfDefs("Args"); + + OS << "bool EvalEmitter::emit" << ID << "("; + for (size_t I = 0, N = Args.size(); I < N; ++I) + OS << "const " << Args[I]->getValueAsString("Name") << " &A" << I << ","; + OS << "const SourceInfo &L) {\n"; + OS << "if (!isActive()) return true;\n"; + OS << "CurrentSource = L;\n"; + + OS << "return " << N; + PrintTypes(OS, TS); + OS << "(S, OpPC"; + for (size_t I = 0, N = Args.size(); I < N; ++I) + OS << ", A" << I; + OS << ");\n"; + OS << "}\n"; + }); + + OS << "#endif\n"; +} + +void ClangOpcodesEmitter::PrintTypes(raw_ostream &OS, ArrayRef Types) { + if (Types.empty()) + return; + OS << "<"; + for (size_t I = 0, N = Types.size(); I < N; ++I) { + if (I != 0) + OS << ", "; + OS << "PT_" << Types[I]->getName(); + } + OS << ">"; +} + +namespace clang { + +void EmitClangOpcodes(RecordKeeper &Records, raw_ostream &OS) { + ClangOpcodesEmitter(Records).run(OS); +} + +} // end namespace clang diff --git a/clang/utils/TableGen/TableGen.cpp b/clang/utils/TableGen/TableGen.cpp --- a/clang/utils/TableGen/TableGen.cpp +++ b/clang/utils/TableGen/TableGen.cpp @@ -47,6 +47,7 @@ GenClangCommentNodes, GenClangDeclNodes, GenClangStmtNodes, + GenClangOpcodes, GenClangSACheckers, GenClangCommentHTMLTags, GenClangCommentHTMLTagsProperties, @@ -129,6 +130,8 @@ "Generate Clang AST declaration nodes"), clEnumValN(GenClangStmtNodes, "gen-clang-stmt-nodes", "Generate Clang AST statement nodes"), + clEnumValN(GenClangOpcodes, "gen-clang-opcodes", + "Generate Clang constexpr interpreter opcodes"), clEnumValN(GenClangSACheckers, "gen-clang-sa-checkers", "Generate Clang Static Analyzer checkers"), clEnumValN(GenClangCommentHTMLTags, "gen-clang-comment-html-tags", @@ -251,6 +254,9 @@ case GenClangStmtNodes: EmitClangASTNodes(Records, OS, "Stmt", ""); break; + case GenClangOpcodes: + EmitClangOpcodes(Records, OS); + break; case GenClangSACheckers: EmitClangSACheckers(Records, OS); break; diff --git a/clang/utils/TableGen/TableGenBackends.h b/clang/utils/TableGen/TableGenBackends.h --- a/clang/utils/TableGen/TableGenBackends.h +++ b/clang/utils/TableGen/TableGenBackends.h @@ -77,6 +77,7 @@ llvm::raw_ostream &OS); void EmitClangCommentCommandList(llvm::RecordKeeper &Records, llvm::raw_ostream &OS); +void EmitClangOpcodes(llvm::RecordKeeper &Records, llvm::raw_ostream &OS); void EmitNeon(llvm::RecordKeeper &Records, llvm::raw_ostream &OS); void EmitFP16(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);