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(EnableNewConstInterp, 1, 0, + "enable the experimental new constant interpreter") +BENIGN_LANGOPT(ForceNewConstInterp, 1, 0, + "force the use of the experimental new constant 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_new_constant_interpreter : Flag<["-"], "fexperimental-new-constant-interpreter">, Group, + HelpText<"Enable the experimental new constant interpreter">, Flags<[CC1Option]>; +def fforce_experimental_new_constant_interpreter : Flag<["-"], "fforce-experimental-new-constant-interpreter">, Group, + HelpText<"Force the use of the experimental new const 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 @@ -81,5 +83,6 @@ LINK_LIBS clangBasic + clangInterp 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" @@ -46,6 +49,7 @@ #include "clang/AST/TypeLoc.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/FixedPoint.h" +#include "clang/Basic/OptionalDiagnostic.h" #include "clang/Basic/TargetInfo.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallBitVector.h" @@ -66,8 +70,8 @@ namespace { struct LValue; - struct CallStackFrame; - struct EvalInfo; + class CallStackFrame; + class EvalInfo; using SourceLocExprScopeGuard = CurrentSourceLocExprScope::SourceLocExprScopeGuard; @@ -222,12 +226,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 +478,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 +573,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 +597,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 +659,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 +680,13 @@ /// we will evaluate. unsigned StepsLeft; + /// Force the use of the experimental new constant interpreter, bailing out + /// with an error if a feature is not supported. + bool ForceNewConstInterp; + + /// Enable the experimental new constant interpreter. + bool EnableNewConstInterp; + /// BottomFrame - The frame in which evaluation started. This must be /// initialized after CurrentCall and CallStackDepth. CallStackFrame BottomFrame; @@ -837,7 +797,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,25 +805,28 @@ /// 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), - BottomFrame(*this, SourceLocation(), nullptr, nullptr, nullptr), - EvaluatingDecl((const ValueDecl *)nullptr), - EvaluatingDeclValue(nullptr), HasActiveDiagnostic(false), - HasFoldFailureDiagnostic(false), - InConstantContext(false), EvalMode(Mode) {} + : Ctx(const_cast(C)), EvalStatus(S), CurrentCall(nullptr), + CallStackDepth(0), NextCallIndex(1), + StepsLeft(getLangOpts().ConstexprStepLimit), + ForceNewConstInterp(getLangOpts().ForceNewConstInterp), + EnableNewConstInterp(ForceNewConstInterp || + getLangOpts().EnableNewConstInterp), + BottomFrame(*this, SourceLocation(), nullptr, nullptr, nullptr), + EvaluatingDecl((const ValueDecl *)nullptr), + EvaluatingDeclValue(nullptr), HasActiveDiagnostic(false), + HasFoldFailureDiagnostic(false), InConstantContext(false), + EvalMode(Mode) {} void setEvaluatingDecl(APValue::LValueBase Base, APValue &Value) { EvaluatingDecl = Base; 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,14 +961,14 @@ /// 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(); } /// Should we continue evaluation as much as possible after encountering a /// construct which can't be reduced to a value? - bool keepEvaluatingAfterFailure() { + bool keepEvaluatingAfterFailure() const override { if (!StepsLeft) return false; @@ -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 << ')'; @@ -12273,6 +12114,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.EnableNewConstInterp) { + 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 +12333,26 @@ 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.EnableNewConstInterp) { + 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: + // Evaluation succeeded and value was set. + return true; + case interp::InterpResult::Bail: + // Evaluate the value again for the tree evaluator to use. + break; + } + } LValue LVal; LVal.set(VD); @@ -12496,18 +12364,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 +13049,18 @@ EvalInfo::EM_PotentialConstantExpression); Info.InConstantContext = true; + // The constexpr VM attempts to compile all methods to bytecode here. + if (Info.EnableNewConstInterp) { + 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/Builtin.h b/clang/lib/AST/Interp/Builtin.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Builtin.h @@ -0,0 +1,27 @@ +//===--- Builtin.h - Builtins 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 +// +//===----------------------------------------------------------------------===// +// +// Builtin dispatch method definition. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_BUILTIN_H +#define LLVM_CLANG_AST_INTERP_BUILTIN_H + +#include "Function.h" + +namespace clang { +namespace interp { +class InterpState; + +bool InterpBuiltin(InterpState &S, CodePtr OpPC, unsigned BuiltinOp); + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Builtin.cpp b/clang/lib/AST/Interp/Builtin.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Builtin.cpp @@ -0,0 +1,103 @@ +//===--- Builtin.cpp - Builtins 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 "Builtin.h" +#include "Interp.h" +#include "InterpState.h" +#include "Pointer.h" +#include "Program.h" +#include "Type.h" +#include "clang/AST/ASTContext.h" +#include "clang/Basic/Builtins.h" + +using namespace clang; +using namespace clang::interp; + +static bool BuiltinLength(InterpState &S, CodePtr OpPC) { + using ResultT = PrimConv::T; + + // Get the pointer to the string and ensure it's an array of primitives. + const auto &Ptr = S.Stk.pop(); + if (!CheckLive(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Read)) + return false; + + Descriptor *D = Ptr.getFieldDesc(); + if (!D->IsArray || D->ElemDesc) + return false; + + // Find the null terminator, starting at the pointed element. + const unsigned Size = D->Size - Ptr.getOffset(); + char *Data = &Ptr.deref(); + switch (D->ElemSize) { + case 1: + for (unsigned Off = 0, I = 0; Off < Size; Off += 1, ++I) { + if (*reinterpret_cast(Data + Off) == 0) { + S.Stk.push(ResultT::from(I)); + return true; + } + } + break; + case 2: + for (unsigned Off = 0, I = 0; Off < Size; Off += 2, ++I) { + if (*reinterpret_cast(Data + Off) == 0) { + S.Stk.push(ResultT::from(I)); + return true; + } + } + break; + case 4: + for (unsigned Off = 0, I = 0; Off < Size; Off += 4, ++I) { + if (*reinterpret_cast(Data + Off) == 0) { + S.Stk.push(ResultT::from(I)); + return true; + } + } + break; + default: + llvm_unreachable("Unsupported character width!"); + } + + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_access_past_end) << AK_Read; + return false; +} + +static void ReportInvalidExpr(InterpState &S, CodePtr OpPC, unsigned Op) { + const char *Name = S.getCtx().BuiltinInfo.getName(Op); + const SourceInfo &Loc = S.Current->getSource(OpPC); + + if (S.getLangOpts().CPlusPlus11) + S.CCEDiag(Loc, diag::note_constexpr_invalid_function) + << /*isConstexpr*/ 0 << /*isConstructor*/ 0 + << (std::string("'") + Name + "'"); + else + S.CCEDiag(Loc, diag::note_invalid_subexpr_in_const_expr); +} + +namespace clang { +namespace interp { + +bool InterpBuiltin(InterpState &S, CodePtr OpPC, unsigned Op) { + switch (Op) { + case Builtin::BIstrlen: + case Builtin::BIwcslen: + ReportInvalidExpr(S, OpPC, Op); + return BuiltinLength(S, OpPC); + case Builtin::BI__builtin_strlen: + case Builtin::BI__builtin_wcslen: + return BuiltinLength(S, OpPC); + default: + // Builtin is not constexpr. + return false; + } +} + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/ByteCodeEmitter.h b/clang/lib/AST/Interp/ByteCodeEmitter.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeEmitter.h @@ -0,0 +1,112 @@ +//===--- ByteCodeEmitter.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 ByteCodeEmitter { +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: + ByteCodeEmitter(Context &Ctx, Program &P) : Ctx(Ctx), P(P) {} + + virtual ~ByteCodeEmitter() {} + + /// 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); + + /// 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/ByteCodeEmitter.cpp b/clang/lib/AST/Interp/ByteCodeEmitter.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeEmitter.cpp @@ -0,0 +1,174 @@ +//===--- ByteCodeEmitter.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 "ByteCodeEmitter.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 ByteCodeEmitter::compileFunc(const FunctionDecl *F) { + // Do not try to compile undefined functions. + if (!F->isDefined(F) || (!F->hasBody() && F->willHaveBody())) + return nullptr; + + // 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 (const ParmVarDecl *PD : F->parameters()) { + PrimType Ty; + if (llvm::Optional T = Ctx.classify(PD->getType())) { + Ty = *T; + } else { + Ty = PT_Ptr; + } + + Descriptor *Desc = P.createDescriptor(PD, Ty); + ParamDescriptors.insert({ParamOffset, {Ty, Desc}}); + Params.insert({PD, ParamOffset}); + ParamOffset += align(primSize(Ty)); + ParamTypes.push_back(Ty); + } + + // Create a handle over the emitted code. + Function *Func = P.createFunction(F, ParamOffset, std::move(ParamTypes), + std::move(ParamDescriptors)); + // Compile the function body. + if (!F->isConstexpr() || !compile(F)) { + // Return a dummy function if compilation failed. + if (BailLocation) + return llvm::make_error(*BailLocation); + else + return Func; + } else { + // Create scopes from descriptors. + llvm::SmallVector Scopes; + for (auto &DS : Descriptors) { + Scopes.emplace_back(std::move(DS)); + } + + // Set the function's code. + Func->setCode(NextLocalOffset, std::move(Code), std::move(SrcMap), + std::move(Scopes)); + return Func; + } +} + +Scope::Local ByteCodeEmitter::createLocal(Descriptor *D) { + NextLocalOffset += sizeof(Block); + unsigned Location = NextLocalOffset; + NextLocalOffset += align(D->AllocSize); + return {Location, D}; +} + +void ByteCodeEmitter::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 ByteCodeEmitter::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 ByteCodeEmitter::bail(const SourceLocation &Loc) { + if (!BailLocation) + BailLocation = Loc; + return false; +} + +template +bool ByteCodeEmitter::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 ByteCodeEmitter::jumpTrue(const LabelTy &Label) { + return emitJt(getOffset(Label), SourceInfo{}); +} + +bool ByteCodeEmitter::jumpFalse(const LabelTy &Label) { + return emitJf(getOffset(Label), SourceInfo{}); +} + +bool ByteCodeEmitter::jump(const LabelTy &Label) { + return emitJmp(getOffset(Label), SourceInfo{}); +} + +bool ByteCodeEmitter::fallthrough(const LabelTy &Label) { + emitLabel(Label); + return true; +} + +//===----------------------------------------------------------------------===// +// Opcode emitters +//===----------------------------------------------------------------------===// + +#define GET_LINK_IMPL +#include "Opcodes.inc" +#undef GET_LINK_IMPL 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,205 @@ +//===--- 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 "ByteCodeEmitter.h" +#include "Pointer.h" +#include "Record.h" +#include "Type.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.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; + /// Program to link to. + Program &P; + +public: + /// Initializes the compiler and the backend emitter. + template + ByteCodeGen(Context &Ctx, Program &P, Tys &&... Args) + : Emitter(Ctx, P, Args...), Ctx(Ctx), P(P) {} + + // Expression visitors - result returned on stack. + bool VisitCastExpr(const CastExpr *CE); + bool VisitIntegerLiteral(const IntegerLiteral *E); + bool VisitParenExpr(const ParenExpr *PE); + bool VisitBinaryOperator(const BinaryOperator *BO); + +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); + + /// Visits an expression and converts it to a boolean. + bool visitBool(const Expr *E); + + 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 *LV, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + bool dereferenceParam(const Expr *LV, const ParmVarDecl *PD, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + bool dereferenceVar(const Expr *LV, const VarDecl *PD, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + bool dereferenceMember(const MemberExpr *PD, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + + /// Compiles a variable declaration. + bool visitVarDecl(const VarDecl *VD); + +protected: + bool compile(const FunctionDecl *F) override; + bool compile(const Expr *E) override; + 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); + } + /// Returns the value of CHAR_BIT. + unsigned getCharBit() const { + auto &ASTContext = Ctx.getASTContext(); + return ASTContext.getTargetInfo().getCharWidth(); + } + + /// Manages the range of a pointer, expanding/narrowing it. + bool adjustRange(const Expr *E, NullaryFn EmitOp); + + /// 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); + + /// Allocates a space storing a local given its type. + llvm::Optional allocateLocal(DeclTy &&Decl, + bool IsExtended = false); + + /// Allocates a global primitive value. + unsigned allocateGlobalPrimitive(const VarDecl *VD, PrimType Ty, + bool IsMutable); + /// Allocates a space storing a global given its type. + llvm::Optional allocateGlobal(const VarDecl *VD); + + /// Returns a record type from a record or pointer type. + const RecordType *getRecordTy(QualType Ty); + + /// Returns a record from a record or pointer type. + Record *getRecord(QualType Ty); + + /// Variable to storage mapping. + llvm::DenseMap Locals; + + /// OpaqueValueExpr to location mapping. + llvm::DenseMap OpaqueExprs; + + /// Current scope. + CompilerScope *Top = nullptr; + + /// Current argument index. + llvm::Optional ArrayIndex; + + /// Switch case mapping. + CaseMap CaseLabels; + + /// Point to break to. + OptLabelTy BreakLabel; + /// Point to continue to. + OptLabelTy ContinueLabel; + /// Default case label. + OptLabelTy DefaultLabel; +}; + +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,858 @@ +//===--- 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 "ByteCodeEmitter.h" +#include "Opcode.h" +#include "Program.h" +#include "State.h" +#include "Type.h" +#include "llvm/ADT/SmallBitVector.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +template using Expected = llvm::Expected; + +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 emitDestruction() {} + + 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->emitDestruction(); } + + 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 emitDestruction() override { + if (!Idx.hasValue()) + return; + this->Ctx->emitDestroy(*Idx, SourceInfo{}); + } + +protected: + /// Index of the scope in the chain. + llvm::Optional Idx; +}; + +/// Scope for storage declared in a compound statement. +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 to handle temporaries in toplevel variable declarations. +template class DeclScope final : public LocalScope { +public: + DeclScope(ByteCodeGen *Ctx) : LocalScope(Ctx) {} + + void addExtended(const Scope::Local &Local) override { + return this->addLocal(Local); + } +}; + +/// Sets the context for break/continue statements. +template +class LoopScope final : public CompilerScope { +public: + using LabelTy = typename ByteCodeGen::LabelTy; + using OptLabelTy = typename ByteCodeGen::OptLabelTy; + + LoopScope(ByteCodeGen *Ctx, LabelTy BreakLabel, + LabelTy ContinueLabel) + : CompilerScope(Ctx), OldBreakLabel(Ctx->BreakLabel), + OldContinueLabel(Ctx->ContinueLabel) { + this->Ctx->BreakLabel = BreakLabel; + this->Ctx->ContinueLabel = ContinueLabel; + } + + ~LoopScope() { + this->Ctx->BreakLabel = OldBreakLabel; + this->Ctx->ContinueLabel = OldContinueLabel; + } + +private: + OptLabelTy OldBreakLabel; + OptLabelTy OldContinueLabel; +}; + +// Sets the context for a switch scope, mapping labels. +template +class SwitchScope final : public CompilerScope { +public: + using LabelTy = typename ByteCodeGen::LabelTy; + using OptLabelTy = typename ByteCodeGen::OptLabelTy; + using CaseMap = typename ByteCodeGen::CaseMap; + + SwitchScope(ByteCodeGen *Ctx, CaseMap &&CaseLabels, + LabelTy BreakLabel, OptLabelTy DefaultLabel) + : CompilerScope(Ctx), OldBreakLabel(Ctx->BreakLabel), + OldDefaultLabel(this->Ctx->DefaultLabel), + OldCaseLabels(std::move(this->Ctx->CaseLabels)) { + this->Ctx->BreakLabel = BreakLabel; + this->Ctx->DefaultLabel = DefaultLabel; + this->Ctx->CaseLabels = std::move(CaseLabels); + } + + ~SwitchScope() { + this->Ctx->BreakLabel = OldBreakLabel; + this->Ctx->DefaultLabel = OldDefaultLabel; + this->Ctx->CaseLabels = std::move(OldCaseLabels); + } + +private: + OptLabelTy OldBreakLabel; + OptLabelTy OldDefaultLabel; + CaseMap OldCaseLabels; +}; + +} // 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); + } + return discard(Exp); + } + return this->bail(S); + } + } +} + +template +bool ByteCodeGen::visitCompoundStmt(const CompoundStmt *CompoundStmt) { + BlockScope Scope(this); + for (auto *InnerStmt : CompoundStmt->body()) + if (!visit(InnerStmt)) + 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; + } + + // Decomposition declarator. + if (auto *DD = dyn_cast(D)) { + return this->bail(DD); + } + } + + return true; +} + +template +bool ByteCodeGen::visitReturnStmt(const ReturnStmt *RS) { + if (const Expr *RE = RS->getRetValue()) { + ExprScope RetScope(this); + QualType RT = RE->getType(); + if (Ctx.isComposite(RT)) { + return this->bail(RS); + } else { + // Primitive types are simply returned. + if (llvm::Optional T = Ctx.classify(RE)) { + if (!this->Visit(RE)) + return false; + for (CompilerScope *C = Top; C; C = C->getParent()) + C->emitDestruction(); + if (!this->emitRet(*T, RS)) + return false; + return true; + } + } + return this->bail(RS); + } else { + for (CompilerScope *C = Top; C; C = C->getParent()) + C->emitDestruction(); + 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 (const DeclStmt *CondDecl = IS->getConditionVariableDeclStmt()) + if (!visitDeclStmt(CondDecl)) + return false; + + if (!visitBool(IS->getCond())) + return false; + + if (const Stmt *Else = IS->getElse()) { + LabelTy LabelElse = this->getLabel(); + LabelTy 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 { + LabelTy LabelEnd = this->getLabel(); + if (!this->jumpFalse(LabelEnd)) + return false; + if (!visit(IS->getThen())) + return false; + this->emitLabel(LabelEnd); + } + + return true; +} + +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_FunctionToPointerDecay: + case CK_ArrayToPointerDecay: + case CK_UserDefinedConversion: + 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 (llvm::Optional 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. + const Expr *LHS = BO->getLHS(); + llvm::Optional TypeLHS = Ctx.classify(LHS->getType()); + if (!TypeLHS) { + return this->bail(BO); + } + const Expr *RHS = BO->getRHS(); + llvm::Optional TypeRHS = Ctx.classify(RHS->getType()); + if (!TypeRHS) { + return this->bail(BO); + } + + if (llvm::Optional T = Ctx.classify(BO->getType())) { + switch (BO->getOpcode()) { + 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 (llvm::Optional 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 (llvm::Optional 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::visitBool(const Expr *E) { + return this->Visit(E); +} + +template +bool ByteCodeGen::dereference( + const Expr *LV, AccessKind AK, llvm::function_ref Direct, + llvm::function_ref Indirect) { + if (auto *DE = dyn_cast(LV)) { + if (!DE->getDecl()->getType()->isReferenceType()) { + if (auto *PD = dyn_cast(DE->getDecl())) + return dereferenceParam(LV, PD, AK, Direct, Indirect); + if (auto *VD = dyn_cast(DE->getDecl())) + return dereferenceVar(LV, VD, AK, Direct, Indirect); + } + } + + if (auto *ME = dyn_cast(LV)) + return dereferenceMember(ME, AK, Direct, Indirect); + + if (llvm::Optional T = Ctx.classify(LV->getType())) { + if (!this->Visit(LV)) + return false; + return Indirect(*T); + } + return false; +} + +template +bool ByteCodeGen::dereferenceParam( + const Expr *LV, const ParmVarDecl *PD, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect) { + llvm::Optional T = Ctx.classify(LV->getType()); + if (!T) + return this->bail(LV); + + 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; + } + + // If the param is a pointer, we can dereference a dummy value. + if (PD->getType()->hasPointerRepresentation()) { + if (AK == AccessKind::Read) { + if (auto Idx = this->P.getOrCreateExtern(PD)) + return this->emitGetPtrGlobal(*Idx, PD); + } + return Direct(*T); + } + + // Value cannot be produced - try to emit pointer. + if (!this->Visit(LV)) + return false; + return Indirect(*T); +} + +template +bool ByteCodeGen::dereferenceVar( + const Expr *LV, const VarDecl *VD, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect) { + llvm::Optional T = Ctx.classify(LV->getType()); + if (!T) + return this->bail(LV); + + 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; + } + + // 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() && VD->hasInit()) { + QualType VT = VD->getType(); + const bool IsRead = AK == AccessKind::Read; + if (VT.isConstQualified() && VT->isFundamentalType() && IsRead) { + if (!this->Visit(VD->getInit())) + return false; + return Direct(*T); + } + } + + // Value cannot be produced - try to emit pointer. + if (!this->Visit(LV)) + return false; + return Indirect(*T); +} + +template +bool ByteCodeGen::dereferenceMember( + const MemberExpr *ME, AccessKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect) { + // Classify the field type. + llvm::Optional T = Ctx.classify(ME->getType()); + if (!T) + return this->bail(ME); + + // Return the record descriptor. + auto *R = getRecord(ME->getBase()->getType()); + if (!R) + return this->bail(ME); + + // TODO: read field. + return this->bail(ME); +} + +template +bool ByteCodeGen::visitVarDecl(const VarDecl *VD) { + auto DT = VD->getType(); + + if (!VD->hasLocalStorage()) { + // No code generation required. + return true; + } + + // Integers, pointers, primitives. + if (llvm::Optional 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 { + // Composite types - allocate storage and initialize it. + return this->bail(VD); + } +} + +template +bool ByteCodeGen::adjustRange(const Expr *E, NullaryFn EmitOp) { + if (!Ctx.isComposite(E->getType())) + return true; + return (this->*EmitOp)(E); +} + +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 +llvm::Optional ByteCodeGen::allocateLocal(DeclTy &&Decl, + bool IsExtended) { + QualType Ty; + + const ValueDecl *Key = nullptr; + bool IsTemporary = false; + if (auto *VD = Decl.dyn_cast()) { + Key = VD; + Ty = VD->getType(); + } + if (auto *E = Decl.dyn_cast()) { + IsTemporary = true; + Ty = E->getType(); + } + + Descriptor *D = P.createDescriptor(std::move(Decl), Ty.getTypePtr(), + !Ty.isConstQualified(), IsTemporary); + if (!D) + return {}; + + Scope::Local Local = this->createLocal(D); + if (Key) + Locals.insert({Key, Local}); + Top->add(Local, IsExtended); + return Local.Offset; +} + +template +unsigned ByteCodeGen::allocateGlobalPrimitive(const VarDecl *VD, + PrimType Ty, + bool IsMutable) { + Descriptor *D = P.createDescriptor(VD, Ty, IsMutable); + return P.emitGlobal(VD, D); +} + +template +llvm::Optional +ByteCodeGen::allocateGlobal(const VarDecl *VD) { + Descriptor *D = P.createDescriptor(VD, VD->getType().getTypePtr(), + !VD->getType().isConstQualified()); + if (!D) + return {}; + return P.emitGlobal(VD, D); +} + +template +const RecordType *ByteCodeGen::getRecordTy(QualType Ty) { + if (auto *PT = dyn_cast(Ty)) + return PT->getPointeeType()->getAs(); + else + return Ty->getAs(); +} + +template +Record *ByteCodeGen::getRecord(QualType Ty) { + if (auto *RecordTy = getRecordTy(Ty)) { + return P.getOrCreateRecord(RecordTy->getDecl()); + } + return nullptr; +} + +template bool ByteCodeGen::compile(const Expr *Exp) { + ExprScope RootScope(this); + if (!this->ConstStmtVisitor, bool>::Visit(Exp)) + return false; + + if (llvm::Optional 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(SourceInfo{}); + else + return this->emitNoRet(SourceInfo{}); +} + +template bool ByteCodeGen::compile(const VarDecl *VD) { + auto VT = VD->getType(); + auto Init = VD->getInit(); + + DeclScope LocalScope(this); + + if (llvm::Optional T = Ctx.classify(VT)) { + // Primitive declarations - compute the value and set it. + if (!this->ConstStmtVisitor, bool>::Visit(Init)) + return false; + + // If the declaration is global, save the value for later use. + unsigned I = allocateGlobalPrimitive(VD, *T, !VT.isConstQualified()); + if (!this->emitDup(*T, VD)) + return false; + if (!this->emitInitGlobal(*T, I, VD)) + return false; + return this->emitRet(*T, 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,33 @@ +set(LLVM_LINK_COMPONENTS + ) + +clang_tablegen(Opcodes.inc + -gen-clang-opcodes + SOURCE Opcodes.td + TARGET Opcodes) + +add_clang_library(clangInterp + Builtin.cpp + ByteCodeEmitter.cpp + ByteCodeGen.cpp + ByteCodeGenError.cpp + Context.cpp + Descriptor.cpp + Disasm.cpp + EvalEmitter.cpp + Frame.cpp + Function.cpp + Interp.cpp + InterpFrame.cpp + InterpStack.cpp + InterpState.cpp + Pointer.cpp + Program.cpp + Record.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,102 @@ +//===--- 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(); + + /// 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; + /// Returns the interpreter stack. + InterpStack &getStack() { return Stk; } + + /// 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,151 @@ +//===--- 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 "ByteCodeEmitter.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().ForceNewConstInterp), + P(new Program(*this)) {} + +Context::~Context() {} + +InterpResult Context::isPotentialConstantExpr(State &Parent, + const FunctionDecl *FD) { + Function *Func = P->getFunction(FD); + if (!Func) { + if (auto R = ByteCodeGen(*this, *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; + } + } + + if (!Func->isConstexpr()) + return InterpResult::Fail; + + APValue Dummy; + return Run(Parent, Func, Dummy); +} + +InterpResult Context::evaluateAsRValue(State &Parent, const Expr *E, + APValue &Result) { + assert(Stk.size() == 0 && "empty stack expected by evaluator"); + ByteCodeGen C(*this, *P, Parent, Stk, Result); + return Check(Parent, C.interpretExpr(E)); +} + +InterpResult Context::evaluateAsInitializer(State &Parent, const VarDecl *VD, + APValue &Result) { + assert(Stk.size() == 0 && "empty stack expected by evaluator"); + ByteCodeGen C(*this, *P, Parent, Stk, Result); + return Check(Parent, C.interpretDecl(VD)); +} + +const LangOptions &Context::getLangOpts() const { return Ctx.getLangOpts(); } + +llvm::Optional Context::classify(QualType T) { + if (T->isReferenceType()) + return PT_Ptr; + + 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; + } + } + + 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; + } + } + + if (T->isNullPtrType()) + return PT_Ptr; + + if (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 { + if (T->isFundamentalType()) + return false; + if (T->isEnumeralType()) + return false; + if (T->hasPointerRepresentation()) + return false; + if (T->isFunctionProtoType()) + return false; + return true; +} + +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 { + 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,158 @@ +//===--- 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; + +/// 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. +using BlockCtorFn = void (*)(Block *Storage, char *FieldPtr, bool IsMutable, + bool IsActive, Descriptor *FieldDesc); + +/// Invoked when a block is destroyed. Invokes the destructors of all +/// non-trivial nested fields of arrays and records. +using BlockDtorFn = void (*)(Block *Storage, char *FieldPtr, + Descriptor *FieldDesc); + +/// Invoked when a block with pointers referencing it goes out of scope. 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. +using BlockMoveFn = void (*)(Block *Storage, char *SrcFieldPtr, + char *DstFieldPtr, Descriptor *FieldDesc); + +/// 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, in host bytes. + const InterpSize ElemSize; + /// Size of the storage, in host bytes. + const InterpSize Size; + /// Size of the allocation (storage + metadata), in host bytes. + const InterpSize AllocSize; + /// 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; + + /// Storage management methods. + const BlockCtorFn CtorFn = nullptr; + const BlockDtorFn DtorFn = nullptr; + 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); + + /// Allocates a descriptor for an array of primitives. + Descriptor(const DeclTy &D, PrimType Type, size_t NumElems, bool IsMutable, + bool IsTemporary); + + /// Allocates a descriptor for an array of composites. + Descriptor(const DeclTy &D, Descriptor *Elem, unsigned NumElems, + bool IsMutable, bool IsTemporary); + + /// Allocates a descriptor for a record. + Descriptor(const DeclTy &D, Record *R, bool IsMutable, bool IsTemporary); + + /// Returns the number of elements stored in the block. + size_t getNumElems() const { return Size / ElemSize; } + + /// Checks if the descriptor is of an array of primitives. + bool isPrimitiveArray() const { return IsArray && !ElemDesc; } +}; + +/// Inline descriptor embedded in structures and arrays. +/// +/// Such descriptors precede all composite array elements and structure fields. +/// If the base of a pointer is not zero, the base points to the end of this +/// structure. The offset field is used to traverse the pointer chain up +/// to the root structure which allocated the object. +struct InlineDescriptor { + /// Offset inside the structure/array. + unsigned Offset; + + /// Flag indicating if the field is mutable or not. + /// Relevant for primitive fields. + unsigned IsMutable : 1; + /// Flag indicating if the field was initialized. + /// Relevant for primitive record fields. + unsigned IsInitialized : 1; + /// Flag indicating if the field is an embedded base class. + unsigned IsBase : 1; + /// Flag indicating if the field is the active member of a union. + unsigned IsActive : 1; + + Descriptor *Desc; +}; + +/// Bitfield tracking the initialisation status of elements of primitive arrays. +/// A pointer to this is embedded at the end of all primitive arrays. +/// If the map was not yet created and nothing was initialied, the pointer to +/// this structure is 0. If the object was fully initialized, the pointer is -1. +struct InitMap { +private: + /// Type packing bits. + using T = uint64_t; + /// Bits stored in a single field. + static constexpr uint64_t PER_FIELD = sizeof(T) * CHAR_BIT; + + /// Initializes the map with no fields set. + InitMap(unsigned N); + + /// Returns a pointer to storage. + T *data(); + +public: + /// Initializes an element. Returns true when object if fully initialized. + bool initialize(unsigned I); + + /// Checks if an element was initialized. + bool isInitialized(unsigned I); + + /// Allocates a map holding N elements. + static InitMap *allocate(unsigned N); + +private: + /// Number of fields initialized. + unsigned UninitFields; +}; + +} // 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,287 @@ +//===--- 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 "Record.h" +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +template +static void ctorTy(Block *, char *Ptr, bool, 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)); +} + +template +static void ctorArrayTy(Block *, char *Ptr, bool, bool, Descriptor *D) { + for (unsigned I = 0, NE = D->getNumElems(); I < NE; ++I) { + new (&reinterpret_cast(Ptr)[I]) T(); + } +} + +template +static void dtorArrayTy(Block *, char *Ptr, Descriptor *D) { + for (unsigned I = 0, NE = D->getNumElems(); I < NE; ++I) { + reinterpret_cast(Ptr)[I].~T(); + } +} + +template +static void moveArrayTy(Block *, char *Src, char *Dst, Descriptor *D) { + for (unsigned I = 0, NE = D->getNumElems(); I < NE; ++I) { + auto *SrcPtr = &reinterpret_cast(Src)[I]; + auto *DstPtr = &reinterpret_cast(Dst)[I]; + new (DstPtr) T(std::move(*SrcPtr)); + } +} + +static void ctorArrayDesc(Block *B, char *Ptr, bool IsMutable, bool IsActive, + Descriptor *D) { + const unsigned NumElems = D->getNumElems(); + const unsigned ElemSize = D->ElemDesc->AllocSize + sizeof(InlineDescriptor); + + unsigned ElemOffset = 0; + for (unsigned I = 0; I < NumElems; ++I, ElemOffset += ElemSize) { + auto *ElemPtr = Ptr + ElemOffset; + auto *Desc = reinterpret_cast(ElemPtr); + auto *ElemLoc = reinterpret_cast(Desc + 1); + auto *SD = D->ElemDesc; + + Desc->Offset = ElemOffset + sizeof(InlineDescriptor); + Desc->Desc = SD; + Desc->IsMutable = IsMutable && D->IsMutable; + Desc->IsInitialized = true; + Desc->IsBase = false; + Desc->IsActive = IsActive; + if (auto Fn = D->ElemDesc->CtorFn) + Fn(B, ElemLoc, Desc->IsMutable, IsActive, D->ElemDesc); + } +} + +static void dtorArrayDesc(Block *B, char *Ptr, Descriptor *D) { + const unsigned NumElems = D->getNumElems(); + const unsigned ElemSize = D->ElemDesc->AllocSize + sizeof(InlineDescriptor); + + unsigned ElemOffset = 0; + for (unsigned I = 0; I < NumElems; ++I, ElemOffset += ElemSize) { + auto *ElemPtr = Ptr + ElemOffset; + auto *Desc = reinterpret_cast(ElemPtr); + auto *ElemLoc = reinterpret_cast(Desc + 1); + if (auto Fn = D->ElemDesc->DtorFn) + Fn(B, ElemLoc, D->ElemDesc); + } +} + +static void moveArrayDesc(Block *B, char *Src, char *Dst, Descriptor *D) { + const unsigned NumElems = D->getNumElems(); + const unsigned ElemSize = D->ElemDesc->AllocSize + sizeof(InlineDescriptor); + + unsigned ElemOffset = 0; + for (unsigned I = 0; I < NumElems; ++I, ElemOffset += ElemSize) { + auto *SrcPtr = Src + ElemOffset; + auto *DstPtr = Dst + ElemOffset; + + auto *SrcDesc = reinterpret_cast(SrcPtr); + auto *SrcElemLoc = reinterpret_cast(SrcDesc + 1); + auto *DstDesc = reinterpret_cast(DstPtr); + auto *DstElemLoc = reinterpret_cast(DstDesc + 1); + + *DstDesc = *SrcDesc; + if (auto Fn = D->ElemDesc->MoveFn) + Fn(B, SrcElemLoc, DstElemLoc, D->ElemDesc); + } +} + +static void ctorRecord(Block *B, char *Ptr, bool IsMutable, bool IsActive, + Descriptor *D) { + const bool IsUnion = D->ElemRecord->isUnion(); + auto CtorSub = [=](unsigned SubOff, Descriptor *SubDesc, bool IsBase) { + auto *Desc = reinterpret_cast(Ptr + SubOff) - 1; + Desc->Offset = SubOff; + Desc->Desc = SubDesc; + Desc->IsMutable = IsMutable && SubDesc->IsMutable; + Desc->IsInitialized = B->isStatic() || SubDesc->IsArray; + Desc->IsBase = IsBase; + Desc->IsActive = IsActive && !IsUnion; + if (auto Fn = SubDesc->CtorFn) + Fn(B, Ptr + SubOff, Desc->IsMutable, Desc->IsActive, SubDesc); + }; + for (const auto &B : D->ElemRecord->bases()) + CtorSub(B.Offset, B.Desc, /*isBase=*/true); + for (const auto &F : D->ElemRecord->fields()) + CtorSub(F.Offset, F.Desc, /*isBase=*/false); + for (const auto &V : D->ElemRecord->virtual_bases()) + CtorSub(V.Offset, V.Desc, /*isBase=*/true); +} + +static void dtorRecord(Block *B, char *Ptr, Descriptor *D) { + auto DtorSub = [=](unsigned SubOff, Descriptor *SubDesc) { + if (auto Fn = SubDesc->DtorFn) + Fn(B, Ptr + SubOff, SubDesc); + }; + for (const auto &F : D->ElemRecord->bases()) + DtorSub(F.Offset, F.Desc); + for (const auto &F : D->ElemRecord->fields()) + DtorSub(F.Offset, F.Desc); + for (const auto &F : D->ElemRecord->virtual_bases()) + DtorSub(F.Offset, F.Desc); +} + +static void moveRecord(Block *B, char *Src, char *Dst, Descriptor *D) { + for (const auto &F : D->ElemRecord->fields()) { + auto FieldOff = F.Offset; + auto FieldDesc = F.Desc; + + *(reinterpret_cast(Dst + FieldOff) - 1) = FieldDesc; + if (auto Fn = FieldDesc->MoveFn) + Fn(B, Src + FieldOff, Dst + FieldOff, FieldDesc); + } +} + +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; + } +} + +static BlockCtorFn getCtorArrayPrim(PrimType Type) { + switch (Type) { + case PT_Ptr: return ctorArrayTy::T>; + default: return nullptr; + } +} + +static BlockDtorFn getDtorArrayPrim(PrimType Type) { + switch (Type) { + case PT_Ptr: return dtorArrayTy::T>; + default: return nullptr; + } +} + +static BlockMoveFn getMoveArrayPrim(PrimType Type) { + switch (Type) { + case PT_Ptr: return moveArrayTy::T>; + default: return nullptr; + } +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsMutable, + bool IsTemporary) + : Source(D), ElemSize(primSize(Type)), Size(ElemSize), AllocSize(Size), + IsMutable(IsMutable), IsTemporary(IsTemporary), CtorFn(getCtorPrim(Type)), + DtorFn(getDtorPrim(Type)), MoveFn(getMovePrim(Type)) { + assert(ElemSize != 0 && "Invalid element size"); + assert(Size != 0 && "Invalid block size"); +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, size_t NumElems, + bool IsMutable, bool IsTemporary) + : Source(D), ElemSize(primSize(Type)), Size(ElemSize * NumElems), + AllocSize(align(Size) + sizeof(InitMap *)), IsMutable(IsMutable), + IsTemporary(IsTemporary), IsArray(true), CtorFn(getCtorArrayPrim(Type)), + DtorFn(getDtorArrayPrim(Type)), MoveFn(getMoveArrayPrim(Type)) { + assert(ElemSize != 0 && "Invalid element size"); + assert(Size != 0 && "Invalid block size"); +} + +Descriptor::Descriptor(const DeclTy &D, Descriptor *Elem, unsigned NumElems, + bool IsMutable, bool IsTemporary) + : Source(D), ElemSize(Elem->AllocSize + sizeof(InlineDescriptor)), + Size(ElemSize * NumElems), AllocSize(Size), ElemDesc(Elem), + IsMutable(IsMutable), IsTemporary(IsTemporary), IsArray(true), + CtorFn(ctorArrayDesc), DtorFn(dtorArrayDesc), MoveFn(moveArrayDesc) { + assert(ElemSize != 0 && "Invalid element size"); + assert(Size != 0 && "Invalid block size"); +} + +Descriptor::Descriptor(const DeclTy &D, Record *R, bool IsMutable, + bool IsTemporary) + : Source(D), ElemSize(R->getFullSize()), Size(ElemSize), AllocSize(Size), + ElemRecord(R), IsMutable(true), IsTemporary(IsTemporary), + CtorFn(ctorRecord), DtorFn(dtorRecord), MoveFn(moveRecord) { + assert(ElemSize != 0 && "Invalid element size"); + assert(Size != 0 && "Invalid block size"); +} + +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"); +} + +InitMap::InitMap(unsigned N) : UninitFields(N) { + for (unsigned I = 0; I < N / PER_FIELD; ++I) { + data()[I] = 0; + } +} + +InitMap::T *InitMap::data() { + auto *Start = reinterpret_cast(this) + align(sizeof(InitMap)); + return reinterpret_cast(Start); +} + +bool InitMap::initialize(unsigned I) { + unsigned Bucket = I / PER_FIELD; + unsigned Mask = 1ull << static_cast(I % PER_FIELD); + if (!(data()[Bucket] & Mask)) { + data()[Bucket] |= Mask; + UninitFields -= 1; + } + return UninitFields == 0; +} + +bool InitMap::isInitialized(unsigned I) { + unsigned Bucket = I / PER_FIELD; + unsigned Mask = 1ull << static_cast(I % PER_FIELD); + return data()[Bucket] & Mask; +} + +InitMap *InitMap::allocate(unsigned N) { + const size_t NumFields = ((N + PER_FIELD - 1) / PER_FIELD); + const size_t Size = align(sizeof(InitMap)) + NumFields * PER_FIELD; + return new (malloc(Size)) InitMap(N); +} 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,69 @@ +//===--- 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)) { + StringRef Name = Cons->getParent()->getName(); + OS << Name << "::" << Name << ":\n"; + } else { + OS << F->getName() << ":\n"; + } + } else { + OS << "<>\n"; + } + + OS << "frame size: " << getFrameSize() << "\n"; + OS << "arg size: " << getArgSize() << "\n"; + OS << "rvo: " << hasRVO() << "\n"; + + auto PrintName = [&OS](const char *Name) { + OS << Name; + for (long I = 0, N = strlen(Name); I < 30 - N; ++I) { + OS << ' '; + } + }; + + for (CodePtr 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, Program &P, State &Parent, 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,164 @@ +//===--- 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; +template using Expected = llvm::Expected; + +EvalEmitter::EvalEmitter(Context &Ctx, Program &P, State &Parent, + 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, CodePtr(), Pointer()); +} + +llvm::Expected EvalEmitter::interpretExpr(const Expr *E) { + if (this->compile(E)) + return true; + if (BailLocation) + return llvm::make_error(*BailLocation); + return false; +} + +llvm::Expected EvalEmitter::interpretDecl(const VarDecl *VD) { + if (this->compile(VD)) + return true; + if (BailLocation) + return llvm::make_error(*BailLocation); + return false; +} + +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->AllocSize); + auto *B = new (Memory.get()) Block(D, /*isStatic=*/false); + B->invokeCtor(); + + // 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; + CurrentLabel = 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,160 @@ +//===--- 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; +class ByteCodeEmitter; +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; + + /// Checks if the first argument is a RVO pointer. + bool hasRVO() const { return ParamTypes.size() != Params.size(); } + + /// 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; + + /// Checks if the function is valid to call in constexpr. + bool isConstexpr() const { return IsValid; } + + /// Checks if the function is virtual. + bool isVirtual() const; + +private: + /// Construct a function representing an actual function. + Function(Program &P, const FunctionDecl *F, unsigned ArgSize, + llvm::SmallVector &&ParamTypes, + llvm::DenseMap &&Params); + + /// Sets the code of a function. + void setCode(unsigned NewFrameSize, std::vector &&NewCode, SourceMap &&NewSrcMap, + llvm::SmallVector &&NewScopes) { + FrameSize = NewFrameSize; + Code = std::move(NewCode); + SrcMap = std::move(NewSrcMap); + Scopes = std::move(NewScopes); + IsValid = true; + } + +private: + friend class Program; + friend class ByteCodeEmitter; + + /// 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; + /// Flag to indicate if the function is valid. + bool IsValid = false; + +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,48 @@ +//===--- 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" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +Function::Function(Program &P, const FunctionDecl *F, unsigned ArgSize, + llvm::SmallVector &&ParamTypes, + llvm::DenseMap &&Params) + : P(P), Loc(F->getBeginLoc()), F(F), ArgSize(ArgSize), + 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; +} + +bool Function::isVirtual() const { + if (auto *M = dyn_cast(F)) + return M->isVirtual(); + return false; +} 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,449 @@ +//===--- 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, while optimising for storage and +/// allowing methods operating on primitive type to compile to fast code. +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 Limits { + using Type = typename Repr::Type; + static const auto Min = std::numeric_limits::min(); + static const auto Max = std::numeric_limits::max(); + }; + template <> struct Limits<1, false> { + static const bool Min = false; + static const bool Max = true; + }; + + // The primitive representing the integral. + using T = typename Repr::Type; + T V; + + /// Primitive representing limits. + using Limit = Limits; + + /// 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; } + + bool operator>(unsigned RHS) const { + return V >= 0 && static_cast(V) > RHS; + } + + 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 unsigned() const { return V; } + explicit operator int64_t() 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); + } + + constexpr static unsigned bitWidth() { return Bits; } + + bool isZero() const { return !V; } + + bool isMin() const { return *this == min(bitWidth()); } + + bool isMinusOne() const { return Signed && V == T(-1); } + + constexpr static bool isSigned() { return Signed; } + + bool isNegative() const { return V < T(0); } + bool isPositive() const { return !isNegative(); } + + 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(Limit::Min); + } + static Integral max(unsigned NumBits) { + return Integral(Limit::Max); + } + + 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 inRange(int64_t Value, unsigned NumBits) { + return CheckRange(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 + static typename std::enable_if::value, bool>::type + CheckRange(int64_t V) { + return Min <= V && V <= Max; + } + + template + static typename std::enable_if::value, bool>::type + CheckRange(int64_t V) { + return V >= 0 && static_cast(V) <= Max; + } +}; + +/// Specialisation for fixed precision integers. +template class Integral<0, Signed> { +private: + template friend class Integral; + + /// Value is stored in an APSInt. + APSInt V; + +public: + /// Integral initialized to an undefined value. + Integral() : V() {} + + /// Construct an integral from a value based on signedness. + explicit Integral(const APSInt &V) : V(V, !Signed) {} + + bool operator<(const Integral &RHS) const { return V < RHS.V; } + bool operator>(const Integral &RHS) const { return V > RHS.V; } + bool operator<=(const Integral &RHS) const { return V <= RHS.V; } + bool operator>=(const Integral &RHS) const { return V >= RHS.V; } + bool operator==(const Integral &RHS) const { return V == RHS.V; } + bool operator!=(const Integral &RHS) const { return V != RHS.V; } + + template + bool operator>(T RHS) const { + constexpr bool ArgSigned = std::is_signed::value; + return V > APSInt(APInt(V.getBitWidth(), RHS, ArgSigned), !ArgSigned); + } + + template + bool operator<(T RHS) const { + constexpr bool ArgSigned = std::is_signed::value; + return V < APSInt(APInt(V.getBitWidth(), RHS, ArgSigned), !ArgSigned); + } + + Integral operator+(const Integral &RHS) const { return Integral(V + RHS.V); } + Integral operator-(const Integral &RHS) const { return Integral(V - RHS.V); } + Integral operator*(const Integral &RHS) const { return Integral(V * RHS.V); } + Integral operator/(const Integral &RHS) const { return Integral(V / RHS.V); } + Integral operator%(const Integral &RHS) const { return Integral(V % RHS.V); } + Integral operator&(const Integral &RHS) const { return Integral(V & RHS.V); } + Integral operator|(const Integral &RHS) const { return Integral(V | RHS.V); } + Integral operator^(const 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); } + + explicit operator off_t() const { + return Signed ? V.getSExtValue() : V.getZExtValue(); + } + explicit operator unsigned() const { + return Signed ? V.getZExtValue() : V.getZExtValue(); + } + + APSInt toAPSInt() const { return V; } + APSInt toAPSInt(unsigned NumBits) const { + if (Signed) + return APSInt(V.sextOrTrunc(NumBits), !Signed); + else + return APSInt(V.zextOrTrunc(NumBits), !Signed); + } + + Integral<0, false> toUnsigned() const { + return Integral<0, false>::from(*this, bitWidth()); + } + + unsigned bitWidth() const { return V.getBitWidth(); } + + bool isZero() const { return V.isNullValue(); } + + bool isMin() const { + if (Signed) + return V.isMinSignedValue(); + else + return V.isMinValue(); + } + + bool isMinusOne() const { return Signed && V.isAllOnesValue(); } + + bool isSigned() const { return Signed; } + + bool isNegative() const { return V.isNegative(); } + bool isPositive() const { return !isNegative(); } + + ComparisonCategoryResult compare(const Integral &RHS) const { + if (V < RHS.V) + return ComparisonCategoryResult::Less; + if (V > RHS.V) + return ComparisonCategoryResult::Greater; + return ComparisonCategoryResult::Equal; + } + + unsigned countLeadingZeros() const { return V.countLeadingZeros(); } + + void print(llvm::raw_ostream &OS) const { OS << V; } + + static Integral min(unsigned NumBits) { + if (Signed) + return Integral(APSInt(APInt::getSignedMinValue(NumBits), !Signed)); + else + return Integral(APSInt(APInt::getMinValue(NumBits), !Signed)); + } + + static Integral max(unsigned NumBits) { + if (Signed) + return Integral(APSInt(APInt::getSignedMaxValue(NumBits), !Signed)); + else + return Integral(APSInt(APInt::getMaxValue(NumBits), !Signed)); + } + + template + static typename std::enable_if::value, Integral>::type + from(T Value, unsigned NumBits) { + const bool SrcSign = std::is_signed::value; + return Integral(APSInt(APInt(NumBits, Value, SrcSign), !SrcSign)); + } + + template + static typename std::enable_if::type + from(Integral Value, unsigned NumBits) { + return Integral(APSInt(APInt(NumBits, Value.V, SrcSign), !SrcSign)); + } + + template + static Integral from(Integral<0, SrcSign> Value, unsigned NumBits) { + if (SrcSign) + return Integral(APSInt(Value.V.sextOrTrunc(NumBits), !Signed)); + else + return Integral(APSInt(Value.V.zextOrTrunc(NumBits), !Signed)); + } + + static Integral zero(unsigned NumBits) { return from(0, NumBits); } + + static bool inRange(int64_t Value, unsigned NumBits) { + APSInt V(APInt(NumBits, Value, true), false); + return min(NumBits).V <= V && V <= max(NumBits).V; + } + + static bool increment(Integral A, Integral *R) { + *R = A + Integral::from(1, A.bitWidth()); + return A.isSigned() && !A.isNegative() && R->isNegative(); + } + + static bool decrement(Integral A, Integral *R) { + *R = A - Integral::from(1, A.bitWidth()); + return !A.isSigned() && A.isNegative() && !R->isNegative(); + } + + static bool add(Integral A, Integral B, unsigned OpBits, Integral *R) { + APSInt Value(A.V.extend(OpBits) + B.V.extend(OpBits)); + *R = Integral(Value.trunc(A.bitWidth())); + return R->V.extend(OpBits) != Value; + } + + static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) { + APSInt Value(A.V.extend(OpBits) - B.V.extend(OpBits)); + *R = Integral(Value.trunc(A.bitWidth())); + return R->V.extend(OpBits) != Value; + } + + static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) { + APSInt Value(A.V.extend(OpBits) * B.V.extend(OpBits)); + *R = Integral(Value.trunc(A.bitWidth())); + return R->V.extend(OpBits) != Value; + } +}; + +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,1193 @@ +//===--- 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 "Builtin.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 Real &V, APValue &R) { + R = APValue(V.toAPFloat()); + return true; +} + +template <> inline bool ReturnValue(const Pointer &Ptr, APValue &R) { + R = Ptr.toAPValue(); + return true; +} + +template <> +inline bool ReturnValue(const FnPointer &Ptr, APValue &R) { + R = Ptr.toAPValue(); + return true; +} + +/// 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 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); + +/// Checks if a method can be called. +bool CheckCallable(InterpState &S, CodePtr OpPC, Function *F); + +template inline bool IsTrue(const T &V) { return !V.isZero(); } +template <> inline bool IsTrue(const Pointer &V) { return !V.isNull(); } +template <> inline bool IsTrue(const FnPointer &V) { return !V.isNull(); } +/// Finds a virtual override and adjusts This to point to the object. +const CXXMethodDecl *VirtualLookup(Pointer &This, uintptr_t Fn); + +//===----------------------------------------------------------------------===// +// 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 +bool CmpHelperEQ(InterpState &S, CodePtr OpPC, CompareFn Fn) { + return CmpHelper(S, OpPC, Fn); +} + +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::hasSameBase(LHS, RHS)) { + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr); + return false; + } else { + unsigned VL = LHS.getByteOffset(); + unsigned VR = RHS.getByteOffset(); + S.Stk.push(BoolT::from(Fn(Compare(VL, VR)))); + return true; + } +} + +template <> +inline bool CmpHelperEQ(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv::T; + const Pointer &RHS = S.Stk.pop(); + const Pointer &LHS = S.Stk.pop(); + + if (!Pointer::hasSameBase(LHS, RHS)) { + S.Stk.push(BoolT::from(Fn(ComparisonCategoryResult::Unordered))); + return true; + } else { + unsigned VL = LHS.getByteOffset(); + unsigned VR = RHS.getByteOffset(); + S.Stk.push(BoolT::from(Fn(Compare(VL, VR)))); + return true; + } +} + +template <> +inline bool CmpHelperEQ(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv::T; + const FnPointer &RHS = S.Stk.pop(); + const FnPointer &LHS = S.Stk.pop(); + if (LHS.asDecl() == RHS.asDecl()) + S.Stk.push(BoolT::from(Fn(ComparisonCategoryResult::Equal))); + else + S.Stk.push(BoolT::from(Fn(ComparisonCategoryResult::Nonequal))); + return true; +} + +template ::T> +bool EQ(InterpState &S, CodePtr OpPC) { + return CmpHelperEQ(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Equal; + }); +} + +template ::T> +bool NE(InterpState &S, CodePtr OpPC) { + return CmpHelperEQ(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; + }); +} + +//===----------------------------------------------------------------------===// +// InRange +//===----------------------------------------------------------------------===// + +template ::T> +bool InRange(InterpState &S, CodePtr OpPC) { + const T RHS = S.Stk.pop(); + const T LHS = S.Stk.pop(); + const T Value = S.Stk.pop(); + + S.Stk.push(LHS <= Value && Value <= RHS); + return true; +} + +//===----------------------------------------------------------------------===// +// Minus, Not, LogicalNot +//===----------------------------------------------------------------------===// + +template ::T> +bool Minus(InterpState &S, CodePtr OpPC) { + const T &Arg = S.Stk.pop(); + + if (Arg.isSigned() && Arg.isMin()) { + // Push the truncated value in case the interpreter continues. + S.Stk.push(T::min(Arg.bitWidth())); + + // Compute the actual value for the diagnostic. + const size_t Bits = Arg.bitWidth() + 1; + const APSInt Value = std::negate()(Arg.toAPSInt(Bits)); + return S.reportOverflow(S.Current->getExpr(OpPC), Value); + } + + S.Stk.push(std::negate()(Arg)); + return true; +} + +template ::T> +bool Not(InterpState &S, CodePtr OpPC) { + S.Stk.push(~S.Stk.pop()); + return true; +} + +template ::T> +bool LogicalNot(InterpState &S, CodePtr OpPC) { + S.Stk.push(!IsTrue(S.Stk.pop())); + return true; +} + +//===----------------------------------------------------------------------===// +// Dup, Pop, Test +//===----------------------------------------------------------------------===// + +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; +} + +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; +} + +template ::T> +bool GetField(InterpState &S, CodePtr OpPC, uint32_t I) { + const Pointer &Obj = S.Stk.peek(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckLoad(S, OpPC, Field)) + return false; + S.Stk.push(Field.deref()); + return true; +} + +template ::T> +bool SetField(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop(); + const Pointer &Obj = S.Stk.peek(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckStore(S, OpPC, Field)) + return false; + Field.deref() = Value; + return true; +} + +template ::T> +bool GetFieldPop(InterpState &S, CodePtr OpPC, uint32_t I) { + const Pointer &Obj = S.Stk.pop(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckLoad(S, OpPC, Field)) + return false; + S.Stk.push(Field.deref()); + return true; +} + +template ::T> +bool SetFieldPop(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop(); + const Pointer &Obj = S.Stk.pop(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckStore(S, OpPC, Field)) + return false; + Field.deref() = Value; + return true; +} + +template ::T> +bool GetThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &Field = S.Current->getThis().atField(I); + if (!CheckLoad(S, OpPC, Field)) + return false; + S.Stk.push(Field.deref()); + return true; +} + +template ::T> +bool SetThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const T &Value = S.Stk.pop(); + const Pointer &Field = S.Current->getThis().atField(I); + if (!CheckStore(S, OpPC, Field)) + return false; + Field.deref() = Value; + return true; +} + +template ::T> +bool GetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Stk.push(S.P.getGlobal(I)); + return true; +} + +template ::T> +bool InitGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.P.setGlobal(I, S.Stk.pop()); + return true; +} + +template ::T> +bool InitThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &Field = S.Current->getThis().atField(I); + Field.deref() = S.Stk.pop(); + Field.initialize(); + return true; +} + +template ::T> +bool InitThisFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &Field = S.Current->getThis().atField(I); + Field.deref() = S.Stk.pop(); + Field.activate(); + Field.initialize(); + return true; +} + + +template ::T> +bool InitField(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop(); + const Pointer &Field = S.Stk.pop().atField(I); + Field.deref() = Value; + Field.activate(); + Field.initialize(); + return true; +} + +template ::T> +bool InitFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.pop(); + const Pointer &Field = Ptr.atField(I); + Field.deref() = Value; + Field.activate(); + Field.initialize(); + 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; +} + +inline bool GetPtrGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Stk.push(S.P.getPtrGlobal(I)); + return true; +} + +inline bool GetPtrField(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop(); + if (!CheckNull(S, OpPC, Ptr, CSK_Field)) + return false; + S.Stk.push(Ptr.atField(Off)); + return true; +} + +inline bool GetPtrThisField(InterpState &S, CodePtr OpPC, uint32_t Off) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &Ptr = S.Current->getThis(); + if (!CheckNull(S, OpPC, Ptr, CSK_Field)) + return false; + S.Stk.push(Ptr.atField(Off)); + return true; +} + +inline bool GetPtrActiveField(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop(); + if (!CheckNull(S, OpPC, Ptr, CSK_Field)) + return false; + Pointer Field = Ptr.atField(Off); + Ptr.deactivate(); + Field.activate(); + S.Stk.push(std::move(Field)); + return true; +} + +inline bool GetPtrActiveThisField(InterpState &S, CodePtr OpPC, uint32_t Off) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!CheckNull(S, OpPC, This, CSK_Field)) + return false; + Pointer Field = This.atField(Off); + This.deactivate(); + Field.activate(); + S.Stk.push(std::move(Field)); + return true; +} + +inline bool GetPtrBase(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop(); + if (!CheckNull(S, OpPC, Ptr, CSK_Base)) + return false; + S.Stk.push(Ptr.atField(Off).narrow()); + return true; +} + +inline bool GetPtrThisBase(InterpState &S, CodePtr OpPC, uint32_t Off) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &Ptr = S.Current->getThis(); + if (!CheckNull(S, OpPC, Ptr, CSK_Base)) + return false; + S.Stk.push(Ptr.atField(Off).narrow()); + return true; +} + +inline bool VirtBaseHelper(InterpState &S, CodePtr OpPC, uintptr_t D, + const Pointer &Ptr) { + if (!CheckNull(S, OpPC, Ptr, CSK_Base)) + return false; + + Pointer Base = Ptr; + while (Base.isBaseClass()) + Base = Base.getBase(); + + auto *Decl = reinterpret_cast(D); + auto *Field = Base.getFieldDesc()->ElemRecord->getVirtualBase(Decl); + S.Stk.push(Base.atField(Field->Offset).narrow()); + return true; +} + +inline bool GetPtrVirtBase(InterpState &S, CodePtr OpPC, uintptr_t D) { + return VirtBaseHelper(S, OpPC, D, S.Stk.pop()); +} + +inline bool GetPtrThisVirtBase(InterpState &S, CodePtr OpPC, uintptr_t D) { + if (S.checkingPotentialConstantExpression()) + return false; + return VirtBaseHelper(S, OpPC, D, S.Current->getThis()); +} + +//===----------------------------------------------------------------------===// +// 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.initialize(); + Ptr.deref() = Value; + return true; +} + +template ::T> +bool InitPop(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.pop(); + if (!CheckInit(S, OpPC, Ptr)) { + return false; + } + Ptr.deref() = Value; + return true; +} + +//===----------------------------------------------------------------------===// +// AddOffset, SubOffset +//===----------------------------------------------------------------------===// + +template bool OffsetHelper(InterpState &S, CodePtr OpPC) { + // Fetch the pointer and the offset. + const T &Offset = S.Stk.pop(); + const Pointer &Ptr = S.Stk.pop(); + if (!CheckNull(S, OpPC, Ptr, CSK_ArrayIndex)) { + return false; + } + + // Get a version of the index comparable to the type. + T Index = T::from(Ptr.getIndex(), Offset.bitWidth()); + + // Compute the largest index into the array. + unsigned MaxIndex = Ptr.size() / Ptr.elemSize(); + + // Helper to report an invalid offset, computed as APSInt. + auto InvalidOffset = [&]() { + const unsigned Bits = Offset.bitWidth(); + APSInt APOffset(Offset.toUnsigned().toAPSInt().zext(Bits + 2), false); + APSInt APIndex(Index.toUnsigned().toAPSInt().zext(Bits + 2), false); + + APSInt NewIndex = Add ? (APIndex + APOffset) : (APIndex - APOffset); + S.CCEDiag(S.Current->getSource(OpPC), diag::note_constexpr_array_index) + << NewIndex + << /*array*/ static_cast(!Ptr.isArray()) + << static_cast(MaxIndex); + return false; + }; + + // If the new offset would be negative, bail out. + if (Add && Offset.isNegative() && (Offset.isMin() || -Offset > Index)) + return InvalidOffset(); + if (!Add && Offset.isPositive() && Index < Offset) + return InvalidOffset(); + + // If the new offset would be out of bounds, bail out. + unsigned MaxOffset = MaxIndex - Ptr.getIndex(); + if (Add && Offset.isPositive() && Offset > MaxOffset) + return InvalidOffset(); + if (!Add && Offset.isNegative() && (Offset.isMin() || -Offset > MaxOffset)) + return InvalidOffset(); + + // Offset is valid - compute it on unsigned. + int64_t WideIndex = static_cast(Index); + int64_t WideOffset = static_cast(Offset); + int64_t Result = Add ? (WideIndex + WideOffset) : (WideIndex - WideOffset); + unsigned NewIndex = static_cast(Result); + S.Stk.push(Ptr.atOffset(NewIndex * Ptr.elemSize())); + return true; +} + +template ::T> +bool AddOffset(InterpState &S, CodePtr OpPC) { + return OffsetHelper(S, OpPC); +} + +template ::T> +bool SubOffset(InterpState &S, CodePtr OpPC) { + return OffsetHelper(S, OpPC); +} + + +//===----------------------------------------------------------------------===// +// Destroy +//===----------------------------------------------------------------------===// + +inline bool Destroy(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->destroy(I); + return true; +} + +//===----------------------------------------------------------------------===// +// Cast, CastFP +//===----------------------------------------------------------------------===// + +template bool Cast(InterpState &S, CodePtr OpPC) { + using T = typename PrimConv::T; + using U = typename PrimConv::T; + S.Stk.push(U::from(S.Stk.pop())); + return true; +} + +template +bool CastFP(InterpState &S, CodePtr OpPC, uint32_t Bits) { + using T = typename PrimConv::T; + using U = typename PrimConv::T; + S.Stk.push(U::from(S.Stk.pop(), Bits)); + return true; +} + +template +bool CastRealFP(InterpState &S, CodePtr OpPC, uintptr_t I) { + using T = typename PrimConv::T; + const auto &Sema = *reinterpret_cast(I); + S.Stk.push(Real::from(S.Stk.pop(), Sema)); + return true; +} + +//===----------------------------------------------------------------------===// +// Inc, Dec +//===----------------------------------------------------------------------===// + +template +using IncDecFn = bool (*) (InterpState &, CodePtr, const T&, T&); + +template +bool Post(InterpState &S, CodePtr OpPC, AccessKinds AK, IncDecFn Op) { + // Bail if not C++14. + if (!S.getLangOpts().CPlusPlus14 && !S.keepEvaluatingAfterFailure()) { + S.FFDiag(S.Current->getSource(OpPC)); + return false; + } + + // Get the pointer to the object to mutate. + const Pointer &Ptr = S.Stk.pop(); + if (!CheckLive(S, OpPC, Ptr, AK)) + return false; + if (!CheckMutable(S, OpPC, Ptr)) + return false; + + T Arg = Ptr.deref(); + S.Stk.push(Arg); + + T R; + if (!Op(S, OpPC, Arg, R)) + return false; + Ptr.deref() = R; + return true; +} + +template class OpAP> +bool IncDecInt(InterpState &S, CodePtr OpPC, const T &Arg, T &R) { + if (std::is_unsigned::value) { + // Unsigned increment/decrement is defined to wrap around. + R = OpAP()(Arg, T::from(1, Arg.bitWidth())); + return true; + } else { + // Signed increment/decrement is undefined, catch that. + if (!OpFW(Arg, &R)) + return true; + // Compute the actual value for the diagnostic. + const size_t Bits = R.bitWidth() + 1; + APSInt One(APInt(Bits, 1, Arg.isSigned()), !Arg.isSigned()); + APSInt Value = OpAP()(Arg.toAPSInt(Bits), One); + return S.reportOverflow(S.Current->getExpr(OpPC), Value); + } +} + +template