diff --git a/clang/docs/ConstantInterpreter.rst b/clang/docs/ConstantInterpreter.rst new file mode 100644 --- /dev/null +++ b/clang/docs/ConstantInterpreter.rst @@ -0,0 +1,192 @@ +==================== +Constant Interpreter +==================== + +.. contents:: + :local: + +Introduction +============ + +The constexpr interpreter aims to replace the existing tree evaluator in clang, improving performance on constructs which are executed inefficiently by the evaluator. The interpreter is activated using the following flags: + +* ``-fexperimental-new-constant-interpreter`` enables the interpreter, falling back to the evaluator for unsupported features +* ``-fforce-experimental-new-constant-interpreter`` forces the use of the interpreter, bailing out if an unsupported feature is encountered + +Bytecode Compilation +==================== + +Bytecode compilation is handled in ``ByteCodeStmtGen.h`` for statements and ``ByteCodeExprGen.h`` for expressions. The compiler has two different backends: one to generate bytecode for functions (``ByteCodeEmitter``) and one to directly evaluate expressions as they are compiled, without generating bytecode (``EvalEmitter``). All functions are compiled to bytecode, while toplevel expressions used in constant contexts are directly evaluated since the bytecode would never be reused. This mechanism aims to pave the way towards replacing the evaluator, improving its performance on functions and loops, while being just as fast on single-use toplevel expressions. + +The interpreter relies on stack-based, strongly-typed opcodes. The glue logic between the code generator, along with the enumeration and description of opcodes, can be found in ``Opcodes.td``. The opcodes are implemented as generic template methods in ``Interp.h`` and instantiated with the relevant primitive types by the interpreter loop or by the evaluating emitter. + +Primitive Types +--------------- + +* ``PT_{U|S}int{8|16|32|64}`` + + Signed or unsigned integers of a specific bit width, implemented using the ```Integral``` type. + +* ``PT_{U|S}intFP`` + + Signed or unsigned integers of an arbitrary, but fixed width used to implement + integral types which are required by the target, but are not supported by the host. + Under the hood, they rely on APValue. The ``Integral`` specialisation for these + types is required by opcodes to share an implementation with fixed integrals. + +* ``PT_Bool`` + + Representation for boolean types, essentially a 1-bit unsigned ``Integral``. + +* ``PT_RealFP`` + + Arbitrary, but fixed precision floating point numbers. Could be specialised in + the future similarly to integers in order to improve floating point performance. + +* ``PT_Ptr`` + + Pointer type, defined in ``"Pointer.h"``. + +* ``PT_FnPtr`` + + Function pointer type, can also be a null function pointer. Defined in ``"Pointer.h"``. + +* ``PT_MemPtr`` + + Member pointer type, can also be a null member pointer. Defined in ``"Pointer.h"`` + +Composite types +--------------- + +The interpreter distinguishes two kinds of composite types: arrays and records. Unions are represented as records, except a single field can be marked as active. The contents of inactive fields are kept until they +are reactivated and overwritten. + + +Bytecode Execution +================== + +Bytecode is executed using a stack-based interpreter. The execution context consists of an ``InterpStack``, along with a chain of ``InterpFrame`` objects storing the call frames. Frames are built by call instructions and destroyed by return instructions. They perform one allocation to reserve space for all locals in a single block. These objects store all the required information to emit stack traces whenever evaluation fails. + +Memory Organisation +=================== + +Memory management in the interpreter relies on 3 data structures: ``Block`` +object which store the data and associated inline metadata, ``Pointer`` objects +which refer to or into blocks, and ``Descriptor`` structures which describe +blocks and subobjects nested inside blocks. + +Blocks +------ + +Blocks contain data interleaved with metadata. They are allocated either statically +in the code generator (globals, static members, dummy parameter values etc.) or +dynamically in the interpreter, when creating the frame containing the local variables +of a function. Blocks are associated with a descriptor that characterises the entire +allocation, along with a few additional attributes: + +* ``IsStatic`` indicates whether the block has static duration in the interpreter, i.e. it is not a local in a frame. + +* ``IsExtern`` indicates that the block was created for an extern and the storage cannot be read or written. + +* ``DeclID`` identifies each global declaration (it is set to an invalid and irrelevant value for locals) in order to prevent illegal writes and reads involving globals and temporaries with static storage duration. + +Static blocks are never deallocated, but local ones might be deallocated even when there are live pointers to them. Pointers are only valid as long as the blocks they point to are valid, so a block with pointers to it whose lifetime ends is kept alive until all pointers to it go out of scope. Since the frame is destroyed on function exit, such blocks are turned into a ``DeadBlock`` and copied to storage managed by the interpreter itself, not the frame. Reads and writes to these blocks are illegal and cause an appropriate diagnostic to be emitted. When the last pointer goes out of scope, dead blocks are also deallocated. + +The lifetime of blocks is managed through 3 methods stored in the descriptor of the block: + +* **CtorFn**: initializes the metadata which is store in the block, alongside actual data. Invokes the default constructors of objects which are not trivial (``Pointer``, ``RealFP``, etc.) +* **DtorFn**: invokes the destructors of non-trivial objects. +* **MoveFn**: moves a block to dead storage. + +Non-static blocks track all the pointers into them through an intrusive doubly-linked list, this is required in order to adjust all pointers when transforming a block into a dead block. + +Descriptors +----------- + +Descriptor are generated at bytecode compilation time and contain information required to determine if a particular memory access is allowed in constexpr. Even though there is a single descriptor object, it encodes information for several kinds of objects: + +* **Primitives** + + A block containing a primitive reserved storage only for the primitive. + +* **Arrays of primitives** + + An array of primitives contains a pointer to an ``InitMap`` storage as its first field: the initialisation map is a bit map indicating all elements of the array which were initialised. If the pointer is null, no elements were initialised, while a value of ``(InitMap)-1`` indicates that the object was fully initialised. when all fields are initialised, the map is deallocated and replaced with that token. + + Array elements are stored sequentially, without padding, after the pointer to the map. + +* **Arrays of composites and records** + + Each element in an array of composites is preceded by an ``InlineDescriptor``. Descriptors and elements are stored sequentially in the block. Records are laid out identically to arrays of composites: each field and base class is preceded by an inline descriptor. The ``InlineDescriptor`` has the following field: + + * **Offset**: byte offset into the array or record, used to step back to the parent array or record. + * **IsConst**: flag indicating if the field is const-qualified. + * **IsInitialized**: flag indicating whether the field or element was initialized. For non-primitive fields, this is only relevant for base classes. + * **IsBase**: flag indicating whether the record is a base class. In that case, the offset can be used to identify the derived class. + * **IsActive**: indicates if the field is the active field of a union. + * **IsMutable**: indicates if the field is marked as mutable. + +Inline descriptors are filled in by the `CtorFn` of blocks, which leaves storage in an uninitialised, but valid state. + +Pointers +-------- + +Pointers track a ``Pointee``, the block to which they point or ``nullptr`` for null pointers, along with a ``Base`` and an ``Offset``. The base identifies the innermost field, while the offset points to an array element relative to the base (including one-past-end pointers). Most subobject the pointer points to in block, while the offset identifies the array element the pointer points to. These two fields allow all pointers to be uniquely identified and disambiguated. + +As an example, consider the following structure: + +.. code-block:: c + + struct A { + struct B { + int x; + int y; + } b; + struct C { + int a; + int b; + } c[2]; + int z; + }; + constexpr A a; + +On the target, ``&a`` and ``&a.b.x`` are equal. So are ``&a.c[0]`` and ``&a.c[0].a``. In the interpreter, all these pointers must be distinguished since the are all allowed to address distinct range of memory. + +In the interpreter, the object would require 240 bytes of storage and would have its field interleaved with metadata. The pointers which can be derived to the object are illustrated in the following diagram: + +:: + + 0 16 32 40 56 64 80 96 112 120 136 144 160 176 184 200 208 224 240 + +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ + + B | D | D | x | D | y | D | D | D | a | D | b | D | D | a | D | b | D | z | + +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ + ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ + | | | | | | | &a.c[0].b | | &a.c[1].b | + a |&a.b.x &a.y &a.c |&a.c[0].a |&a.c[1].a | + &a.b &a.c[0] &a.c[1] &a.z + +The ``Base`` offset of all pointers points to the start of a field or an array and is preceded by an inline descriptor (unless ``Base == 0``, pointing to the root). All the relevant attributes can be read from either the inline descriptor or the descriptor of the block. + +Array elements are identified by the ``Offset`` field of pointers, pointing to past the inline descriptors for composites and before the actual data in the case of primitive arrays. The ``Offset`` points to the offset where primitives can be read from. As an example, ``a.c + 1`` would have the same base as ``a.c`` since it is an element of ``a.c``, but its offset would point to ``&a.c[1]``. The ``*`` operation narrows the scope of the pointer, adjusting the base to ``&a.c[1]``. The reverse operator, ``&``, expands the scope of ``&a.c[1]``, turning it into ``a.c + 1``. When a one-past-end pointer is narrowed, its offset is set to ``-1`` to indicate that it is an invalid value (expanding returns the past-the-end pointer). As a special case, narrowing ``&a.c`` results in ``&a.c[0]``. The `narrow` and `expand` methods can be used to follow the chain of equivalent pointers. + +TODO +==== + +Missing Language Features +------------------------- + +* Definition of externs must override previous declaration +* Changing the active field of unions +* ``typeid`` +* ``volatile`` +* ``__builtin_constant_p`` +* ``std::initializer_list`` +* lambdas +* range-based for loops +* ``vector_size`` +* ``dynamic_cast`` + +Known Bugs +---------- + +* If execution fails, memory storing APInts and APFloats is leaked when the stack is cleared 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 @@ -834,6 +834,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 constant 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" @@ -783,6 +784,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 << ')'; @@ -12276,6 +12117,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; @@ -12483,11 +12336,29 @@ 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; + + SourceLocation DeclLoc = VD->getLocation(); + QualType DeclTy = VD->getType(); + + 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 CheckConstantExpression(Info, DeclLoc, DeclTy, Value); + case interp::InterpResult::Bail: + // Evaluate the value again for the tree evaluator to use. + break; + } + } LValue LVal; LVal.set(VD); @@ -12497,20 +12368,19 @@ // zero-initialized before any other initialization takes place. // This behavior is not present in C. if (Ctx.getLangOpts().CPlusPlus && !VD->hasLocalStorage() && - !VD->getType()->isReferenceType()) { - ImplicitValueInitExpr VIE(VD->getType()); - if (!EvaluateInPlace(Value, InitInfo, LVal, &VIE, + !DeclTy->isReferenceType()) { + ImplicitValueInitExpr VIE(DeclTy); + 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, DeclLoc, DeclTy, Value); } /// isEvaluatable - Call EvaluateAsRValue to see if this expression can be @@ -13185,6 +13055,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/Block.h b/clang/lib/AST/Interp/Block.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Block.h @@ -0,0 +1,142 @@ +//===--- Block.h - Allocated blocks for the interpreter ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the classes describing allocated blocks. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_BLOCK_H +#define LLVM_CLANG_AST_INTERP_BLOCK_H + +#include "Descriptor.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ComparisonCategories.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/Support/raw_ostream.h" + +namespace clang { +namespace interp { +class Block; +class DeadBlock; +class Context; +class InterpState; +class Pointer; +class Function; +enum PrimType : unsigned; + +/// A memory block, either on the stack or in the heap. +/// +/// The storage described by the block immediately follows it in memory. +class Block { +public: + // Creates a new block. + Block(const llvm::Optional &DeclID, Descriptor *Desc, + bool IsStatic = false, bool IsExtern = false) + : DeclID(DeclID), IsStatic(IsStatic), IsExtern(IsExtern), Desc(Desc) {} + + Block(Descriptor *Desc, bool IsStatic = false, bool IsExtern = false) + : DeclID((unsigned)-1), IsStatic(IsStatic), IsExtern(IsExtern), + Desc(Desc) {} + + /// Returns the block's descriptor. + Descriptor *getDescriptor() const { return Desc; } + /// Checks if the block has any live pointers. + bool hasPointers() const { return Pointers; } + /// Checks if the block is extern. + bool isExtern() const { return IsExtern; } + /// Checks if the block has static storage duration. + bool isStatic() const { return IsStatic; } + /// Checks if the block is temporary. + bool isTemporary() const { return Desc->IsTemporary; } + /// Checks if the block is constant. + bool isConst() const { return Desc->IsConst; } + /// Returns the size of the block. + InterpSize getSize() const { return Desc->getAllocSize(); } + /// Returns the declaration ID. + llvm::Optional getDeclID() const { return DeclID; } + + /// Returns a pointer to the stored data. + char *data() { return reinterpret_cast(this + 1); } + + /// Returns a view over the data. + template + T &deref() { return *reinterpret_cast(data()); } + + /// Invokes the constructor. + void invokeCtor() { + std::memset(data(), 0, getSize()); + if (Desc->CtorFn) + Desc->CtorFn(this, data(), Desc->IsConst, Desc->IsMutable, + /*isActive=*/true, Desc); + } + +protected: + friend class Pointer; + friend class DeadBlock; + friend class InterpState; + + Block(Descriptor *Desc, bool IsExtern, bool IsStatic, bool IsDead) + : IsStatic(IsStatic), IsExtern(IsExtern), IsDead(true), Desc(Desc) {} + + // Deletes a dead block at the end of its lifetime. + void cleanup(); + + // Pointer chain management. + void addPointer(Pointer *P); + void removePointer(Pointer *P); + void movePointer(Pointer *From, Pointer *To); + + /// Start of the chain of pointers. + Pointer *Pointers = nullptr; + /// Unique identifier of the declaration. + llvm::Optional DeclID; + /// Flag indicating if the block has static storage duration. + bool IsStatic = false; + /// Flag indicating if the block is an extern. + bool IsExtern = false; + /// Flag indicating if the pointer is dead. + bool IsDead = false; + /// Pointer to the stack slot descriptor. + Descriptor *Desc; +}; + +/// Descriptor for a dead block. +/// +/// Dead blocks are chained in a double-linked list to deallocate them +/// whenever pointers become dead. +class DeadBlock { +public: + /// Copies the block. + DeadBlock(DeadBlock *&Root, Block *Blk); + + /// Returns a pointer to the stored data. + char *data() { return B.data(); } + +private: + friend class Block; + friend class InterpState; + + void free(); + + /// Root pointer of the list. + DeadBlock *&Root; + /// Previous block in the list. + DeadBlock *Prev; + /// Next block in the list. + DeadBlock *Next; + + /// Actual block storing data and tracking pointers. + Block B; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Block.cpp b/clang/lib/AST/Interp/Block.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/Block.cpp @@ -0,0 +1,87 @@ +//===--- Block.cpp - Allocated blocks for the interpreter -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the classes describing allocated blocks. +// +//===----------------------------------------------------------------------===// + +#include "Block.h" +#include "Pointer.h" + +using namespace clang; +using namespace clang::interp; + + + +void Block::addPointer(Pointer *P) { + if (IsStatic) + return; + if (Pointers) + Pointers->Prev = P; + P->Next = Pointers; + P->Prev = nullptr; + Pointers = P; +} + +void Block::removePointer(Pointer *P) { + if (IsStatic) + return; + if (Pointers == P) + Pointers = P->Next; + if (P->Prev) + P->Prev->Next = P->Next; + if (P->Next) + P->Next->Prev = P->Prev; +} + +void Block::cleanup() { + if (Pointers == nullptr && IsDead) + (reinterpret_cast(this + 1) - 1)->free(); +} + +void Block::movePointer(Pointer *From, Pointer *To) { + if (IsStatic) + return; + To->Prev = From->Prev; + if (To->Prev) + To->Prev->Next = To; + To->Next = From->Next; + if (To->Next) + To->Next->Prev = To; + if (Pointers == From) + Pointers = To; + + From->Prev = nullptr; + From->Next = nullptr; +} + +DeadBlock::DeadBlock(DeadBlock *&Root, Block *Blk) + : Root(Root), B(Blk->Desc, Blk->IsStatic, Blk->IsExtern, /*isDead=*/true) { + // Add the block to the chain of dead blocks. + if (Root) + Root->Prev = this; + + Next = Root; + Prev = nullptr; + Root = this; + + // Transfer pointers. + B.Pointers = Blk->Pointers; + for (Pointer *P = Blk->Pointers; P; P = P->Next) + P->Pointee = &B; +} + +void DeadBlock::free() { + if (Prev) + Prev->Next = Next; + if (Next) + Next->Prev = Prev; + if (Root == this) + Root = Next; + ::free(this); +} 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,96 @@ +//===--- 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 (!Ptr.inPrimitiveArray()) + return false; + if (!S.CheckLoad(OpPC, Ptr)) + return false; + + // Find the null terminator, starting at the pointed element. + const unsigned Size = Ptr.getSize() - Ptr.getOffset(); + char *Data = &Ptr.narrow().deref(); + switch (Ptr.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!"); + } + + S.FFDiag(S.getSource(OpPC), 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); + + if (S.getLangOpts().CPlusPlus11) + S.CCEDiag(S.getSource(OpPC), diag::note_constexpr_invalid_function) + << /*isConstexpr*/ 0 << /*isConstructor*/ 0 + << (std::string("'") + Name + "'"); + else + S.CCEDiag(S.getSource(OpPC), 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 visitFunc(const FunctionDecl *E) = 0; + virtual bool visitExpr(const Expr *E) = 0; + virtual bool visitDecl(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,175 @@ +//===--- 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. + QualType Ty = F->getReturnType(); + if (!Ty->isVoidType() && !Ctx.classify(Ty)) { + 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() || !visitFunc(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->getAllocSize()); + 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/ByteCodeExprGen.h b/clang/lib/AST/Interp/ByteCodeExprGen.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeExprGen.h @@ -0,0 +1,480 @@ +//===--- ByteCodeExprGen.h - Code generator for expressions -----*- 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_BYTECODEEXPRGEN_H +#define LLVM_CLANG_AST_INTERP_BYTECODEEXPRGEN_H + +#include "ByteCodeEmitter.h" +#include "EvalEmitter.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 RecordScope; +template class VariableScope; +template class DeclScope; +template class OptionScope; + +/// Compilation context for expressions. +template +class ByteCodeExprGen : public ConstStmtVisitor, bool>, + public Emitter { +protected: + // Emitters for opcodes of various arities. + using NullaryFn = bool (ByteCodeExprGen::*)(const SourceInfo &); + using UnaryFn = bool (ByteCodeExprGen::*)(PrimType, const SourceInfo &); + using BinaryFn = bool (ByteCodeExprGen::*)(PrimType, PrimType, + const SourceInfo &); + + // Aliases for types defined in the emitter. + using LabelTy = typename Emitter::LabelTy; + using AddrTy = typename Emitter::AddrTy; + + // Reference to a function generating the pointer of an initialized object.s + using InitFnRef = std::function; + + /// Current compilation context. + Context &Ctx; + /// Program to link to. + Program &P; + +public: + /// Initializes the compiler and the backend emitter. + template + ByteCodeExprGen(Context &Ctx, Program &P, Tys &&... Args) + : Emitter(Ctx, P, Args...), Ctx(Ctx), P(P) {} + + // Expression visitors - result returned on stack. + bool VisitDeclRefExpr(const DeclRefExpr *E); + bool VisitCastExpr(const CastExpr *E); + bool VisitConstantExpr(const ConstantExpr *E); + bool VisitIntegerLiteral(const IntegerLiteral *E); + bool VisitFloatingLiteral(const FloatingLiteral *E); + bool VisitStringLiteral(const StringLiteral *E); + bool VisitCharacterLiteral(const CharacterLiteral *E); + bool VisitParenExpr(const ParenExpr *E); + bool VisitBinaryOperator(const BinaryOperator *E); + bool VisitUnaryPostInc(const UnaryOperator *E); + bool VisitUnaryPostDec(const UnaryOperator *E); + bool VisitUnaryPreInc(const UnaryOperator *E); + bool VisitUnaryPreDec(const UnaryOperator *E); + bool VisitUnaryAddrOf(const UnaryOperator *E); + bool VisitUnaryDeref(const UnaryOperator *E); + bool VisitUnaryPlus(const UnaryOperator *E); + bool VisitUnaryMinus(const UnaryOperator *E); + bool VisitUnaryNot(const UnaryOperator *E); + bool VisitUnaryLNot(const UnaryOperator *E); + bool VisitUnaryReal(const UnaryOperator *E); + bool VisitUnaryImag(const UnaryOperator *E); + bool VisitConditionalOperator(const ConditionalOperator *E); + bool VisitBinaryConditionalOperator(const BinaryConditionalOperator *E); + bool VisitMemberExpr(const MemberExpr *E); + bool VisitCallExpr(const CallExpr *E); + bool VisitArraySubscriptExpr(const ArraySubscriptExpr *E); + bool VisitExprWithCleanups(const ExprWithCleanups *E); + bool VisitCompoundLiteralExpr(const CompoundLiteralExpr *E); + bool VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *E); + bool VisitImplicitValueInitExpr(const ImplicitValueInitExpr *E); + bool VisitSubstNonTypeTemplateParmExpr(const SubstNonTypeTemplateParmExpr *E); + bool VisitUnaryExprOrTypeTraitExpr(const UnaryExprOrTypeTraitExpr *E); + bool VisitSizeOfPackExpr(const SizeOfPackExpr *E); + bool VisitOpaqueValueExpr(const OpaqueValueExpr *E); + bool VisitArrayInitLoopExpr(const ArrayInitLoopExpr *E); + bool VisitArrayInitIndexExpr(const ArrayInitIndexExpr *E); + bool VisitInitListExpr(const InitListExpr *E); + bool VisitTypeTraitExpr(const TypeTraitExpr *E); + bool VisitCXXConstructExpr(const CXXConstructExpr *E); + bool VisitCXXMemberCallExpr(const CXXMemberCallExpr *E); + bool VisitCXXNullPtrLiteralExpr(const CXXNullPtrLiteralExpr *E); + bool VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *E); + bool VisitCXXThisExpr(const CXXThisExpr *E); + bool VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *E); + bool VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *E); + bool VisitCXXScalarValueInitExpr(const CXXScalarValueInitExpr *E); + bool VisitCXXThrowExpr(const CXXThrowExpr *E); + bool VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *E); + bool VisitCXXTypeidExpr(const CXXTypeidExpr *E); + bool VisitCXXReinterpretCastExpr(const CXXReinterpretCastExpr *E); + bool VisitCXXDynamicCastExpr(const CXXDynamicCastExpr *E); + bool VisitCXXInheritedCtorInitExpr(const CXXInheritedCtorInitExpr *E); + bool VisitCXXStdInitializerListExpr(const CXXStdInitializerListExpr *E); + +protected: + bool visitExpr(const Expr *E) override; + bool visitDecl(const VarDecl *VD) override; + +protected: + /// Emits scope cleanup instructions. + void emitCleanup(); + + /// 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); + Record *getRecord(const RecordDecl *RD); + + /// Perform an action if a record field is found. + bool withField(const FieldDecl *F, + llvm::function_ref GenField); + + /// Returns the size int bits of an integer. + unsigned getIntWidth(QualType Ty) { + auto &ASTContext = Ctx.getASTContext(); + return ASTContext.getIntWidth(Ty); + } + + /// Returns the applicable fp semantics. + const fltSemantics *getFltSemantics(QualType Ty) { + return &Ctx.getASTContext().getFloatTypeSemantics(Ty); + } + + /// Returns the value of CHAR_BIT. + unsigned getCharBit() const { + auto &ASTContext = Ctx.getASTContext(); + return ASTContext.getTargetInfo().getCharWidth(); + } + + /// Canonicalizes an array type. + const ConstantArrayType *getAsConstantArrayType(QualType AT) { + return Ctx.getASTContext().getAsConstantArrayType(AT); + } + + /// Classifies a type. + llvm::Optional classify(const Expr *E) const { + return E->isGLValue() ? PT_Ptr : classify(E->getType()); + } + llvm::Optional classify(QualType Ty) const { + return Ctx.classify(Ty); + } + + /// Checks if a pointer needs adjustment. + bool needsAdjust(QualType Ty) const { + if (llvm::Optional T = classify(Ty)) + return T != PT_MemPtr && T != PT_FnPtr; + return true; + } + + /// Classifies a known primitive type + PrimType classifyPrim(QualType Ty) const { + if (auto T = classify(Ty)) { + return *T; + } + llvm_unreachable("not a primitive type"); + } + + /// Evaluates an expression for side effects and discards the result. + bool discard(const Expr *E); + /// Evaluates an expression and places result on stack. + bool visit(const Expr *E); + /// Compiles an initializer for a local. + bool visitInitializer(const Expr *E, InitFnRef GenPtr); + + /// Visits an expression and converts it to a boolean. + bool visitBool(const Expr *E); + + /// Visits a base class initializer. + bool visitBaseInitializer(const Expr *Init, InitFnRef GenBase); + + /// Visits an initializer for a local. + bool visitLocalInitializer(const Expr *Init, unsigned I) { + return visitInitializer(Init, [this, I, Init] { + return this->emitGetPtrLocal(I, Init); + }); + } + + /// Visits an initializer for a global. + bool visitGlobalInitializer(const Expr *Init, unsigned I) { + return visitInitializer(Init, [this, I, Init] { + return this->emitGetPtrGlobal(I, Init); + }); + } + + /// Visits a delegated initializer. + bool visitThisInitializer(const Expr *I) { + return visitInitializer(I, [this, I] { return this->emitThis(I); }); + } + + /// 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); + +private: + friend class VariableScope; + friend class LocalScope; + friend class RecordScope; + friend class DeclScope; + friend class OptionScope; + + /// Emits a zero initializer. + bool visitZeroInitializer(PrimType T, const Expr *E); + + /// Emits a direct function call. + bool emitFunctionCall(const FunctionDecl *Callee, llvm::Optional T, + const Expr *Call); + /// Emits a direct method call. + bool emitMethodCall(const CXXMethodDecl *Callee, llvm::Optional T, + const Expr *Call); + + /// Compiles an offset calculator. + bool visitOffset(const Expr *Ptr, const Expr *Offset, const Expr *E, + UnaryFn OffsetFn); + + /// Fetches a member of a structure given by a pointer. + bool visitIndirectMember(const BinaryOperator *E); + + /// Compiles simple or compound assignments. + bool visitAssign(PrimType T, const BinaryOperator *BO); + bool visitShiftAssign(PrimType RHS, BinaryFn F, const BinaryOperator *BO); + bool visitCompoundAssign(PrimType RHS, UnaryFn F, const BinaryOperator *BO); + bool visitPtrAssign(PrimType RHS, UnaryFn F, const BinaryOperator *BO); + + /// Emits a cast between two types. + bool emitConv(PrimType From, QualType FromTy, PrimType To, QualType ToTy, + const Expr *Cast); + + bool visitShortCircuit(const BinaryOperator *E); + + enum class DerefKind { + /// Value is read and pushed to stack. + Read, + /// Direct method generates a value which is written. Returns pointer. + Write, + /// Direct method receives the value, pushes mutated value. Returns pointer. + ReadWrite, + }; + + /// 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, DerefKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + bool dereferenceParam(const Expr *LV, PrimType T, const ParmVarDecl *PD, + DerefKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + bool dereferenceVar(const Expr *LV, PrimType T, const VarDecl *PD, + DerefKind AK, llvm::function_ref Direct, + llvm::function_ref Indirect); + bool dereferenceMember(const MemberExpr *PD, PrimType T, DerefKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect); + + /// 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); + } + + /// Compiles a list of arguments. + bool visitArguments(QualType CalleeTy, ArrayRef Args); + /// Compiles an argument. + bool visitArgument(const Expr *E, bool Discard); + + /// Visits a constant function invocation. + bool getPtrConstFn(const FunctionDecl *FD, const Expr *E); + /// Returns a pointer to a variable declaration. + bool getPtrVarDecl(const VarDecl *VD, const Expr *E); + + /// Returns the index of a global. + llvm::Optional getGlobalIdx(const VarDecl *VD); + + /// Compiles a string initializer. + bool visitStringInitializer(const StringLiteral *S); + /// Compiles an array initializer. + bool visitArrayInitializer(const ConstantArrayType *AT, + const Expr *E, + llvm::function_ref Elem); + /// Visits a record initializer. + bool visitRecordInitializer(const RecordType *RT, const InitListExpr *List); + /// Visits a complex initializer. + bool visitComplexInitializer(const ComplexType *CT, const InitListExpr *List); + + /// Visits a cast to complex. + bool visitCastToComplex(const CastExpr *CE); + + /// Zero initializer for a record. + bool visitZeroInitializer(const Expr *E, const RecordDecl *RD); + + /// Registers an opaque expression. + bool visitOpaqueExpr(const OpaqueValueExpr *Expr); + /// Visits a conditional operator. + bool visitConditionalOperator(const AbstractConditionalOperator *CO); + + /// Materializes a composite. + bool materialize(const Expr *Alloc, const Expr *Init, bool IsConst, + bool IsGlobal, bool IsExtended); + + /// Emits the initialized pointer. + bool emitInitFn() { + assert(InitFn && "missing initializer"); + return (*InitFn)(); + } + + /// Returns the alignment of a type. + CharUnits getAlignOfType(QualType T, bool IsPreferred); + + /// Returns the alignment of an expresion. + CharUnits getAlignOfExpr(const Expr *E, bool IsPreferred); + +protected: + /// Variable to storage mapping. + llvm::DenseMap Locals; + + /// OpaqueValueExpr to location mapping. + llvm::DenseMap OpaqueExprs; + + /// Current scope. + VariableScope *VarScope = nullptr; + + /// Current argument index. + llvm::Optional ArrayIndex; + + /// Flag indicating if return value is to be discarded. + bool DiscardResult = false; + + /// Expression being initialized. + llvm::Optional InitFn = {}; + + /// Enumeration of initializer kinds. + enum class InitKind { + /// Regular invocation. + ROOT, + /// Base class initializer. + BASE, + /// Activates a union field. + UNION, + }; + + /// Initialiser kinds for the current object. + InitKind Initialiser = InitKind::ROOT; +}; + +extern template class ByteCodeExprGen; +extern template class ByteCodeExprGen; + +/// Scope chain managing the variable lifetimes. +template class VariableScope { +public: + virtual ~VariableScope() { Ctx->VarScope = 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() {} + + VariableScope *getParent() { return Parent; } + +protected: + VariableScope(ByteCodeExprGen *Ctx) + : Ctx(Ctx), Parent(Ctx->VarScope) { + Ctx->VarScope = this; + } + + /// ByteCodeExprGen instance. + ByteCodeExprGen *Ctx; + /// Link to the parent scope. + VariableScope *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 VariableScope { +public: + LocalScope(ByteCodeExprGen *Ctx) : VariableScope(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. + Optional Idx; +}; + +/// Scope for storage declared in a compound statement. +template class BlockScope final : public LocalScope { +public: + BlockScope(ByteCodeExprGen *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(ByteCodeExprGen *Ctx) : LocalScope(Ctx) {} + + void addExtended(const Scope::Local &Local) override { + this->Parent->addLocal(Local); + } +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/ByteCodeExprGen.cpp b/clang/lib/AST/Interp/ByteCodeExprGen.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeExprGen.cpp @@ -0,0 +1,2552 @@ +//===--- ByteCodeExprGen.cpp - Code generator for expressions ---*- 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 "ByteCodeExprGen.h" +#include "ByteCodeEmitter.h" +#include "ByteCodeGenError.h" +#include "Context.h" +#include "Function.h" +#include "Program.h" +#include "State.h" +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +template using Expected = llvm::Expected; +template using Optional = llvm::Optional; + +namespace clang { +namespace interp { + +/// Scope used to handle temporaries in toplevel variable declarations. +template class DeclScope final : public LocalScope { +public: + DeclScope(ByteCodeExprGen *Ctx, const VarDecl *VD) + : LocalScope(Ctx), Scope(Ctx->P, VD) {} + + void addExtended(const Scope::Local &Local) override { + return this->addLocal(Local); + } + +private: + Program::DeclScope Scope; +}; + +/// Scope used to handle initialization methods. +template class OptionScope { +public: + using InitFnRef = typename ByteCodeExprGen::InitFnRef; + using InitKind = typename ByteCodeExprGen::InitKind; + using ChainedInitFnRef = std::function; + + /// Root constructor, compiling or discarding primitives. + OptionScope(ByteCodeExprGen *Ctx, bool NewDiscardResult) + : Ctx(Ctx), OldDiscardResult(Ctx->DiscardResult), + OldInitFn(std::move(Ctx->InitFn)), + OldInitialiser(Ctx->Initialiser) { + Ctx->DiscardResult = NewDiscardResult; + Ctx->InitFn = llvm::Optional{}; + Ctx->Initialiser = InitKind::ROOT; + } + + /// Root constructor, setting up compilation state. + OptionScope(ByteCodeExprGen *Ctx, InitFnRef NewInitFn, + InitKind NewInitialiser = InitKind::ROOT) + : Ctx(Ctx), OldDiscardResult(Ctx->DiscardResult), + OldInitFn(std::move(Ctx->InitFn)), + OldInitialiser(Ctx->Initialiser) { + Ctx->DiscardResult = true; + Ctx->InitFn = NewInitFn; + Ctx->Initialiser = NewInitialiser; + } + + ~OptionScope() { + Ctx->DiscardResult = OldDiscardResult; + Ctx->InitFn = std::move(OldInitFn); + Ctx->Initialiser = OldInitialiser; + } + +protected: + /// Extends the chain of initialisation pointers. + OptionScope(ByteCodeExprGen *Ctx, ChainedInitFnRef NewInitFn, + InitKind NewInitialiser) + : Ctx(Ctx), OldDiscardResult(Ctx->DiscardResult), + OldInitFn(std::move(Ctx->InitFn)), OldInitialiser(Ctx->Initialiser) { + assert(OldInitFn && "missing initializer"); + Ctx->InitFn = [this, NewInitFn] { return NewInitFn(*OldInitFn); }; + Ctx->Initialiser = NewInitialiser; + } + +private: + /// Parent context. + ByteCodeExprGen *Ctx; + /// Old discard flag to restore. + bool OldDiscardResult; + /// Old pointer emitter to restore. + llvm::Optional OldInitFn; + /// Base flag to restore. + InitKind OldInitialiser; +}; + +// Scope which initialises a base class. +template class BaseScope : public OptionScope { +public: + using ChainedInitFnRef = typename OptionScope::ChainedInitFnRef; + using InitKind = typename OptionScope::InitKind; + BaseScope(ByteCodeExprGen *Ctx, ChainedInitFnRef FieldFn) + : OptionScope(Ctx, FieldFn, InitKind::BASE) {} +}; + +// Scope which initialises a union field. +template class UnionScope : public OptionScope { +public: + using ChainedInitFnRef = typename OptionScope::ChainedInitFnRef; + using InitKind = typename OptionScope::InitKind; + UnionScope(ByteCodeExprGen *Ctx, ChainedInitFnRef FieldFn) + : OptionScope(Ctx, FieldFn, InitKind::UNION) {} +}; + +// Scope which initialises a record field or array element. +template class FieldScope : public OptionScope { +public: + using ChainedInitFnRef = typename OptionScope::ChainedInitFnRef; + using InitKind = typename OptionScope::InitKind; + FieldScope(ByteCodeExprGen *Ctx, ChainedInitFnRef FieldFn) + : OptionScope(Ctx, FieldFn, InitKind::ROOT) {} +}; + +} // namespace interp +} // namespace clang + +template +bool ByteCodeExprGen::VisitDeclRefExpr(const DeclRefExpr *DE) { + if (DiscardResult) + return true; + + if (auto *PD = dyn_cast(DE->getDecl())) { + QualType Ty = PD->getType(); + auto It = this->Params.find(PD); + if (It == this->Params.end()) { + // Pointers to parameters are not constant expressions. + return this->emitTrap(DE); + } else { + // Generate a pointer to a parameter. + if (Ty->isReferenceType() || !classify(Ty)) + return this->emitGetParamPtr(It->second, DE); + else + return this->emitGetPtrParam(It->second, DE); + } + } + if (auto *VD = dyn_cast(DE->getDecl())) { + auto It = Locals.find(VD); + if (It == Locals.end()) { + return getPtrVarDecl(VD, DE); + } else { + // Generate a pointer to a local. + if (VD->getType()->isReferenceType()) + return this->emitGetLocal(PT_Ptr, It->second.Offset, DE); + else + return this->emitGetPtrLocal(It->second.Offset, DE); + } + } + if (auto *ED = dyn_cast(DE->getDecl())) { + QualType Ty = ED->getType(); + if (Optional T = classify(Ty)) + return this->emitConst(*T, getIntWidth(Ty), ED->getInitVal(), DE); + return this->bail(DE); + } + if (auto *FD = dyn_cast(DE->getDecl())) { + if (auto *CD = dyn_cast(DE->getDecl())) + if (!CD->isStatic()) + return this->emitConstMem(CD, DE); + return getPtrConstFn(FD, DE); + } + if (auto *FD = dyn_cast(DE->getDecl())) + return this->emitConstMem(FD, DE); + + // TODO: compile other decls. + return this->bail(DE); +} + +template +bool ByteCodeExprGen::VisitCastExpr(const CastExpr *CE) { + auto *SubExpr = CE->getSubExpr(); + switch (CE->getCastKind()) { + + case CK_LValueToRValue: { + return dereference( + CE->getSubExpr(), DerefKind::Read, + [](PrimType) { + // Value loaded - nothing to do here. + return true; + }, + [this, CE](PrimType T) { + // Pointer on stack - dereference it. + if (!this->emitLoadPop(T, CE)) + return false; + return DiscardResult ? this->emitPop(T, CE) : true; + }); + } + + case CK_IntegralToBoolean: { + if (DiscardResult) + return discard(SubExpr); + + if (!visit(SubExpr)) + return false; + + return this->emitTest(*classify(SubExpr->getType()), CE); + } + + case CK_IntegralCast: { + if (DiscardResult) + return discard(SubExpr); + + if (!visit(SubExpr)) + return false; + + QualType ArgTy = SubExpr->getType(); + QualType RetTy = CE->getType(); + auto ArgT = *classify(ArgTy); + auto RetT = *classify(RetTy); + if (isFixedIntegral(RetT)) + return this->emitCastFP(ArgT, RetT, getIntWidth(RetTy), CE); + else + return this->emitCast(ArgT, RetT, CE); + } + + case CK_FloatingCast: + case CK_IntegralToFloating: { + if (DiscardResult) + return discard(SubExpr); + + if (!visit(SubExpr)) + return false; + + QualType ArgTy = SubExpr->getType(); + QualType RetTy = CE->getType(); + auto ArgT = *classify(ArgTy); + return this->emitCastRealFP(ArgT, getFltSemantics(RetTy), CE); + } + + case CK_FloatingToIntegral: { + if (!visit(SubExpr)) + return false; + + QualType RetTy = CE->getType(); + PrimType ArgT = *classify(SubExpr->getType()); + PrimType RetT = *classify(RetTy); + if (isFixedIntegral(RetT)) { + if (!this->emitCastRealFPToAluFP(ArgT, RetT, getIntWidth(RetTy), CE)) + return false; + } else { + if (!this->emitCastRealFPToAlu(ArgT, RetT, CE)) + return false; + } + + return DiscardResult ? this->emitPop(RetT, CE) : true; + } + + case CK_NullToPointer: + case CK_NullToMemberPointer: + // Emit a null pointer, avoiding redundancy when casting from nullptr. + if (!isa(SubExpr)) { + if (!discard(SubExpr)) + return false; + } + if (DiscardResult) + return true; + return visitZeroInitializer(classifyPrim(CE->getType()), CE); + + case CK_PointerToBoolean: { + if (DiscardResult) + return discard(SubExpr); + else + return visit(SubExpr) && this->emitTestPtr(CE); + } + + case CK_ArrayToPointerDecay: + case CK_AtomicToNonAtomic: + case CK_ConstructorConversion: + case CK_FunctionToPointerDecay: + case CK_NonAtomicToAtomic: + case CK_NoOp: + case CK_UserDefinedConversion: + return this->Visit(SubExpr); + + case CK_ToVoid: + return discard(SubExpr); + + case CK_IntegralRealToComplex: + case CK_FloatingRealToComplex: + return visitCastToComplex(CE); + + case CK_DerivedToBase: + case CK_UncheckedDerivedToBase: { + if (!visit(SubExpr)) + return false; + + const Record *R = getRecord(SubExpr->getType()); + if (!R) + return false; + + for (auto *Step : CE->path()) { + auto *Decl = Step->getType()->getAs()->getDecl(); + + const Record::Base *Base; + if (Step->isVirtual()) { + Base = R->getVirtualBase(Decl); + if (!this->emitGetPtrVirtBase(Decl, CE)) + return false; + } else { + Base = R->getBase(Decl); + if (!this->emitGetPtrBase(Base->Offset, CE)) + return false; + } + + R = Base->Record; + } + + return DiscardResult ? this->emitPopPtr(CE) : true; + } + + case CK_BaseToDerived: { + if (!visit(SubExpr)) + return false; + if (!this->emitCastToDerived(CE, CE)) + return false; + return DiscardResult ? this->emitPopPtr(CE) : true; + } + + case CK_DerivedToBaseMemberPointer: { + if (!visit(SubExpr)) + return false; + for (auto *Step : CE->path()) { + auto *R = Step->getType()->getAs()->getDecl(); + if (!this->emitCastMemberToBase(cast(R), CE)) + return false; + } + return DiscardResult ? this->emitPopMemPtr(CE) : true; + } + + case CK_BaseToDerivedMemberPointer: { + if (CE->path_empty()) + return discard(SubExpr); + + if (!visit(SubExpr)) + return false; + + // Single cast step from base to derived. + auto Step = [this, CE](const Type *T) { + auto *R = cast(T->getAs()->getDecl()); + return this->emitCastMemberToDerived(R, CE); + }; + + // Base-to-derived member pointer casts store the path in derived-to-base + // order, so iterate backwards. The CXXBaseSpecifier also provides us with + // the wrong end of the derived->base arc, so stagger the path by one class. + typedef std::reverse_iterator Rev; + for (auto It = Rev(CE->path_end() - 1); It != Rev(CE->path_begin()); ++It) { + if (!Step((*It)->getType().getTypePtr())) + return false; + } + // The final type is encoded in the type of the cast. + if (!Step(CE->getType()->getAs()->getClass())) + return false; + return DiscardResult ? this->emitPopMemPtr(CE) : true; + } + + case CK_BitCast: { + if (!this->Visit(SubExpr)) + return false; + QualType T = CE->getType(); + if (!T->isVoidPointerType()) { + if (T->isMemberFunctionPointerType()) + return false; + if (T->isMemberPointerType()) + return false; + if (T->isFunctionPointerType()) + return false; + return this->emitPointerBitCast(SubExpr); + } + return true; + } + + case CK_IntegralToPointer: + case CK_PointerToIntegral: { + if (!this->Visit(SubExpr)) + return false; + return this->emitPointerBitCast(SubExpr); + } + + default: { + // TODO: implement other casts. + return this->bail(CE); + } + } +} + +template +bool ByteCodeExprGen::VisitConstantExpr(const ConstantExpr *CE) { + if (DiscardResult) + return true; + + switch (CE->getResultStorageKind()) { + case ConstantExpr::RSK_Int64: { + QualType Ty = CE->getType(); + PrimType T = *classify(Ty); + return this->emitConst(T, getIntWidth(Ty), CE->getResultAsAPSInt(), CE); + } + case ConstantExpr::RSK_APValue: { + return this->bail(CE); + } + case ConstantExpr::RSK_None: { + return this->Visit(CE->getSubExpr()); + } + } +} + +template +bool ByteCodeExprGen::VisitIntegerLiteral(const IntegerLiteral *LE) { + if (DiscardResult) + return true; + + auto Val = LE->getValue(); + QualType LitTy = LE->getType(); + if (Optional T = classify(LitTy)) + return emitConst(*T, getIntWidth(LitTy), LE->getValue(), LE); + return this->bail(LE); +} + +template +bool ByteCodeExprGen::VisitFloatingLiteral(const FloatingLiteral *E) { + if (DiscardResult) + return true; + return this->emitConstRealFP(E, E); +} + +template +bool ByteCodeExprGen::VisitStringLiteral(const StringLiteral *E) { + if (InitFn) + return visitStringInitializer(E); + if (DiscardResult) + return true; + return this->emitGetPtrGlobal(P.createGlobalString(E), E); +} + +template +bool ByteCodeExprGen::VisitCharacterLiteral( + const CharacterLiteral *CE) { + if (DiscardResult) + return true; + + QualType CharTy = CE->getType(); + if (Optional T = classify(CharTy)) { + APInt Char(sizeof(unsigned) * CHAR_BIT, CE->getValue(), false); + return this->emitConst(*T, getIntWidth(CharTy), Char, CE); + } + return this->bail(CE); +} + +template +bool ByteCodeExprGen::VisitParenExpr(const ParenExpr *PE) { + return this->Visit(PE->getSubExpr()); +} + +template +bool ByteCodeExprGen::VisitBinaryOperator(const BinaryOperator *BO) { + const Expr *LHS = BO->getLHS(); + const Expr *RHS = BO->getRHS(); + + // Deal with operations which have composite or void types. + switch (BO->getOpcode()) { + case BO_PtrMemD: + case BO_PtrMemI: + return visitIndirectMember(BO); + case BO_Comma: + if (!discard(LHS)) + return false; + if (!this->Visit(RHS)) + return false; + return true; + default: + break; + } + + // Typecheck the args. + Optional LT = classify(LHS->getType()); + Optional RT = classify(RHS->getType()); + if (!LT || !RT) { + return this->bail(BO); + } + + if (Optional T = classify(BO->getType())) { + switch (BO->getOpcode()) { + case BO_Assign: + return visitAssign(*T, BO); + + case BO_AddAssign: + if (LT == PT_Ptr) + return visitPtrAssign(*RT, &ByteCodeExprGen::emitAddOffset, BO); + else + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitAdd, BO); + case BO_SubAssign: + if (LT == PT_Ptr) + return visitPtrAssign(*RT, &ByteCodeExprGen::emitSubOffset, BO); + else + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitSub, BO); + + case BO_MulAssign: + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitMul, BO); + case BO_DivAssign: + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitDiv, BO); + case BO_RemAssign: + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitRem, BO); + case BO_AndAssign: + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitAnd, BO); + case BO_XorAssign: + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitXor, BO); + case BO_OrAssign: + return visitCompoundAssign(*RT, &ByteCodeExprGen::emitOr, BO); + + case BO_ShlAssign: + if (Ctx.getLangOpts().OpenCL) + return this->bail(BO); + return visitShiftAssign(*RT, &ByteCodeExprGen::emitShl, BO); + + case BO_ShrAssign: + if (Ctx.getLangOpts().OpenCL) + return this->bail(BO); + return visitShiftAssign(*RT, &ByteCodeExprGen::emitShr, BO); + + case BO_Add: { + if (*LT == PT_Ptr && *RT != PT_Ptr) + return visitOffset(LHS, RHS, BO, &ByteCodeExprGen::emitAddOffset); + if (*LT != PT_Ptr && *RT == PT_Ptr) + return visitOffset(RHS, LHS, BO, &ByteCodeExprGen::emitAddOffset); + break; + } + case BO_Sub: { + if (*LT == PT_Ptr && *RT == PT_Ptr) { + if (!visit(LHS)) + return false; + if (!visit(RHS)) + return false; + if (isFixedIntegral(*T)) { + if (!this->emitPtrDiffFP(*T, getIntWidth(BO->getType()), BO)) + return false; + } else { + if (!this->emitPtrDiff(*T, BO)) + return false; + } + return DiscardResult ? this->emitPop(*T, BO) : true; + } + if (*LT == PT_Ptr && *RT != PT_Ptr) + return visitOffset(LHS, RHS, BO, &ByteCodeExprGen::emitSubOffset); + break; + } + + case BO_LOr: + case BO_LAnd: + return visitShortCircuit(BO); + + default: + break; + } + + if (!visit(LHS)) + return false; + if (!visit(RHS)) + return false; + + auto Discard = [this, T, BO](bool Result) { + if (!Result) + return false; + return DiscardResult ? this->emitPop(*T, BO) : true; + }; + + switch (BO->getOpcode()) { + case BO_EQ: + return Discard(this->emitEQ(*LT, BO)); + case BO_NE: + return Discard(this->emitNE(*LT, BO)); + case BO_LT: + return Discard(this->emitLT(*LT, BO)); + case BO_LE: + return Discard(this->emitLE(*LT, BO)); + case BO_GT: + return Discard(this->emitGT(*LT, BO)); + case BO_GE: + return Discard(this->emitGE(*LT, BO)); + case BO_Or: + return Discard(this->emitOr(*T, BO)); + case BO_And: + return Discard(this->emitAnd(*T, BO)); + case BO_Xor: + return Discard(this->emitXor(*T, BO)); + case BO_Rem: + return Discard(this->emitRem(*T, BO)); + case BO_Div: + return Discard(this->emitDiv(*T, BO)); + case BO_Sub: + return Discard(this->emitSub(*T, BO)); + case BO_Add: + return Discard(this->emitAdd(*T, BO)); + case BO_Mul: + return Discard(this->emitMul(*T, BO)); + case BO_Shr: + if (Ctx.getLangOpts().OpenCL) + return this->bail(BO); + return Discard(this->emitShr(*LT, *RT, BO)); + case BO_Shl: + if (Ctx.getLangOpts().OpenCL) + return this->bail(BO); + return Discard(this->emitShl(*LT, *RT, BO)); + default: + return this->bail(BO); + } + } + + return this->bail(BO); +} + +template +bool ByteCodeExprGen::VisitUnaryPlus(const UnaryOperator *UO) { + return this->Visit(UO->getSubExpr()); +} + +template +bool ByteCodeExprGen::VisitUnaryMinus(const UnaryOperator *UM) { + if (!visit(UM->getSubExpr())) + return false; + + if (Optional T = classify(UM->getType())) { + if (!this->emitMinus(*T, UM)) + return false; + return DiscardResult ? this->emitPop(*T, UM) : true; + } + + return this->bail(UM); +} + +template +bool ByteCodeExprGen::VisitUnaryDeref(const UnaryOperator *E) { + if (!this->Visit(E->getSubExpr())) + return false; + if (DiscardResult) + return true; + if (needsAdjust(E->getType())) + return this->emitNarrowPtr(E); + return true; +} + +template +bool ByteCodeExprGen::VisitUnaryAddrOf(const UnaryOperator *E) { + if (!this->Visit(E->getSubExpr())) + return false; + if (DiscardResult) + return true; + if (needsAdjust(E->getType())) + return this->emitExpandPtr(E); + return true; +} + +template +bool ByteCodeExprGen::VisitUnaryPostInc(const UnaryOperator *E) { + if (!visit(E->getSubExpr())) + return false; + PrimType T = *classify(E->getType()); + if (!this->emitPostInc(T, E)) + return false; + return DiscardResult ? this->emitPop(T, E) : true; +} + +template +bool ByteCodeExprGen::VisitUnaryPostDec(const UnaryOperator *E) { + if (!visit(E->getSubExpr())) + return false; + PrimType T = *classify(E->getType()); + if (!this->emitPostDec(T, E)) + return false; + return DiscardResult ? this->emitPop(T, E) : true; +} + +template +bool ByteCodeExprGen::VisitUnaryPreInc(const UnaryOperator *E) { + if (!visit(E->getSubExpr())) + return false; + PrimType T = *classify(E->getType()); + if (!this->emitPreInc(T, E)) + return false; + return DiscardResult ? this->emitPopPtr(E) : true; +} + +template +bool ByteCodeExprGen::VisitUnaryPreDec(const UnaryOperator *E) { + if (!visit(E->getSubExpr())) + return false; + PrimType T = *classify(E->getType()); + if (!this->emitPreDec(T, E)) + return false; + return DiscardResult ? this->emitPopPtr(E) : true; +} + +template +bool ByteCodeExprGen::VisitUnaryNot(const UnaryOperator *UO) { + if (!this->Visit(UO->getSubExpr())) + return false; + PrimType T = *classify(UO->getType()); + return DiscardResult ? true : this->emitNot(T, UO); +} + +template +bool ByteCodeExprGen::VisitUnaryLNot(const UnaryOperator *UO) { + if (!this->Visit(UO->getSubExpr())) + return false; + PrimType T = *classify(UO->getType()); + return DiscardResult ? true : this->emitLogicalNot(T, UO); +} + +template +bool ByteCodeExprGen::VisitUnaryReal(const UnaryOperator *UO) { + const Expr *SubExpr = UO->getSubExpr(); + if (!isa(SubExpr->getType())) + return this->Visit(SubExpr); + if (!visit(SubExpr)) + return false; + if (!this->emitRealElem(UO)) + return false; + return DiscardResult ? this->emitPop(PT_Ptr, UO) : true; +} + +template +bool ByteCodeExprGen::VisitUnaryImag(const UnaryOperator *UO) { + const Expr *SubExpr = UO->getSubExpr(); + if (!isa(SubExpr->getType())) + return this->Visit(SubExpr); + if (!visit(SubExpr)) + return false; + if (!this->emitImagElem(UO)) + return false; + return DiscardResult ? this->emitPop(PT_Ptr, UO) : true; +} + +template +bool ByteCodeExprGen::VisitConditionalOperator( + const ConditionalOperator *CO) { + return visitConditionalOperator(CO); +} + +template +bool ByteCodeExprGen::VisitBinaryConditionalOperator( + const BinaryConditionalOperator *BO) { + if (!visitOpaqueExpr(BO->getOpaqueValue())) + return false; + return visitConditionalOperator(BO); +} + +template +bool ByteCodeExprGen::visitConditionalOperator( + const AbstractConditionalOperator *CO) { + if (!visitBool(CO->getCond())) + return false; + LabelTy LabelFalse = this->getLabel(); + LabelTy LabelEnd = this->getLabel(); + if (!this->jumpFalse(LabelFalse)) + return false; + if (!this->Visit(CO->getTrueExpr())) + return false; + if (!this->jump(LabelEnd)) + return false; + this->emitLabel(LabelFalse); + if (!this->Visit(CO->getFalseExpr())) + return false; + if (!this->fallthrough(LabelEnd)) + return false; + return true; +} + +template +bool ByteCodeExprGen::VisitMemberExpr(const MemberExpr *ME) { + // Fetch a pointer to the required field. + if (auto *FD = dyn_cast(ME->getMemberDecl())) { + return withField(FD, [this, FD, ME](const Record::Field *F) { + const bool IsReference = FD->getType()->isReferenceType(); + if (isa(ME->getBase())) { + if (IsReference) { + if (!this->emitGetThisFieldPtr(F->Offset, ME)) + return false; + } else { + if (!this->emitGetPtrThisField(F->Offset, ME)) + return false; + } + } else { + if (!visit(ME->getBase())) + return false; + if (IsReference) { + if (!this->emitGetFieldPopPtr(F->Offset, ME)) + return false; + } else { + if (!this->emitGetPtrField(F->Offset, ME)) + return false; + } + } + return DiscardResult ? this->emitPopPtr(ME) : true; + }); + } + + // Emit the enum constant value of the enum field. + if (auto *ED = dyn_cast(ME->getMemberDecl())) + return this->Visit(ED->getInitExpr()); + + // Pointer to static field. + if (auto *VD = dyn_cast(ME->getMemberDecl())) + return DiscardResult ? true : getPtrVarDecl(VD, ME); + + // Pointer to static method or method. + if (auto *MD = dyn_cast(ME->getMemberDecl())) { + assert(MD->isStatic() && "Method is not static"); + return DiscardResult ? true : getPtrConstFn(MD, ME); + } + + llvm_unreachable("Invalid member field"); +} + +template +bool ByteCodeExprGen::VisitCallExpr(const CallExpr *CE) { + // Emit the pointer to build the return value into. + if (InitFn && !emitInitFn()) + return false; + + auto Args = llvm::makeArrayRef(CE->getArgs(), CE->getNumArgs()); + auto T = classify(CE->getCallReturnType(Ctx.getASTContext())); + + // Emit the call. + if (unsigned BuiltinOp = CE->getBuiltinCallee()) { + // If the callee is a builtin, lower args and invoke. + if (!visitArguments(CE->getCallee()->getType(), Args)) + return false; + if (!this->emitBuiltin(BuiltinOp, CE)) + return false; + return DiscardResult && T ? this->emitPop(*T, CE) : true; + } else if (const FunctionDecl *Callee = CE->getDirectCallee()) { + // Emit a direct call if the callee is known. + if (isa(Callee) && !Callee->isStatic()) { + if (!visitArguments(CE->getCallee()->getType(), Args.slice(1))) + return false; + if (Args.size() < 1 || !visit(Args[0])) + return false; + return emitMethodCall(dyn_cast(Callee), T, CE); + } else { + // Lower arguments. + if (!visitArguments(CE->getCallee()->getType(), Args)) + return false; + return emitFunctionCall(Callee, T, CE); + } + } else { + // Function pointer call. + if (!visitArguments(CE->getCallee()->getType(), Args)) + return false; + if (!visit(CE->getCallee())) + return false; + if (!this->emitIndirectCall(CE)) + return false; + return DiscardResult && T ? this->emitPop(*T, CE) : true; + } +} + +template +bool ByteCodeExprGen::VisitCXXConstructExpr( + const CXXConstructExpr *E) { + CXXConstructorDecl *CD = E->getConstructor(); + + // Helper to invoke the constructor to initialize the pointer in InitFn. + auto InvokeConstructor = [this, E, CD] { + auto Args = llvm::makeArrayRef(E->getArgs(), E->getNumArgs()); + if (E->requiresZeroInitialization() && CD->isTrivial()) { + // Do not invoke constructor, fill in with 0. + auto *RT = E->getType()->getAs(); + return visitZeroInitializer(E, RT->getDecl()); + } else { + // Avoid materialization if elidable. + if (E->isElidable()) { + if (auto *ME = dyn_cast(E->getArg(0))) + return this->Visit(ME->GetTemporaryExpr()); + } + + // Invoke constructor with 'this' as the pointer. + if (!visitArguments(E->getConstructor()->getType(), Args)) + return false; + if (!emitInitFn()) + return false; + return emitMethodCall(E->getConstructor(), {}, E); + } + }; + + // Invoke the constructor on each array element or on the single record. + if (auto *CAT = dyn_cast(E->getType())) { + uint64_t NumElems = CAT->getSize().getZExtValue(); + for (unsigned I = 0; I < NumElems; ++I) { + FieldScope Scope(this, [this, I, E](InitFnRef Base) { + if (!Base()) + return false; + if (!this->emitConstUint32(I, E)) + return false; + if (!this->emitAddOffsetUint32(E)) + return false; + return this->emitNarrowPtr(E); + }); + if (!InvokeConstructor()) + return false; + } + return true; + } + + return InvokeConstructor(); +} + +template +bool ByteCodeExprGen::VisitCXXMemberCallExpr( + const CXXMemberCallExpr *CE) { + // Emit the pointer to build the return value into. + if (InitFn && !emitInitFn()) + return false; + + // Emit the arguments, this pointer and the call. + auto T = classify(CE->getType()); + auto Args = llvm::makeArrayRef(CE->getArgs(), CE->getNumArgs()); + + // Identify member calls with direct targets, invoking them. + if (auto *MD = dyn_cast_or_null(CE->getDirectCallee())) { + if (!visitArguments(MD->getType(), Args)) + return false; + + // Lower the 'this' pointer. + if (!visit(CE->getImplicitObjectArgument())) + return false; + + // Direct member call. + if (!MD->isVirtual()) + return emitMethodCall(MD, T, CE); + + // Indirect virtual call. + if (!this->emitVirtualInvoke(MD, CE)) + return false; + return DiscardResult && T ? this->emitPop(*T, CE) : true; + } + + // Pattern match the callee for indirect calls to avoid materializing + // the bound member function pointer on the stack. + const Expr *Callee = CE->getCallee(); + if (Callee->getType()->isSpecificBuiltinType(BuiltinType::BoundMember)) { + auto *BO = dyn_cast(Callee->IgnoreParens()); + switch (BO->getOpcode()) { + case BO_PtrMemD: + case BO_PtrMemI: + if (!visitArguments(BO->getRHS()->getType(), Args)) + return false; + // Emit 'this' pointer. + if (!visit(BO->getLHS())) + return false; + // Emit member function. + if (!visit(BO->getRHS())) + return false; + // Emit invocation. + if (!this->emitIndirectInvoke(CE)) + return false; + return DiscardResult && T ? this->emitPop(*T, CE) : true; + default: + llvm_unreachable("invalid indirect callee"); + } + } + + llvm_unreachable("invalid member call expression callee"); +} + +template +bool ByteCodeExprGen::emitFunctionCall(const FunctionDecl *Callee, + Optional T, + const Expr *E) { + if (Expected Func = P.getOrCreateFunction(Callee)) { + if (*Func) { + if (!this->emitCall(*Func, E)) + return false; + } else { + if (!this->emitNoCall(Callee, E)) + return false; + } + } else { + consumeError(Func.takeError()); + return this->bail(E); + } + return DiscardResult && T ? this->emitPop(*T, E) : true; +} + +template +bool ByteCodeExprGen::emitMethodCall(const CXXMethodDecl *Callee, + Optional T, + const Expr *E) { + if (Expected Func = P.getOrCreateFunction(Callee)) { + if (*Func) { + if (!this->emitInvoke(*Func, E)) + return false; + } else { + if (!this->emitNoInvoke(Callee, E)) + return false; + } + } else { + consumeError(Func.takeError()); + return this->bail(E); + } + return DiscardResult && T ? this->emitPop(*T, E) : true; +} + +template +bool ByteCodeExprGen::VisitArraySubscriptExpr( + const ArraySubscriptExpr *E) { + if (!visit(E->getBase())) + return false; + auto *Idx = E->getIdx(); + if (!visit(Idx)) + return false; + if (!this->emitAddOffset(*classify(Idx->getType()), E)) + return false; + return DiscardResult ? this->emitPopPtr(E) : this->emitNarrowPtr(E); +} + +template +bool ByteCodeExprGen::VisitExprWithCleanups( + const ExprWithCleanups *CE) { + return this->Visit(CE->getSubExpr()); +} + +template +bool ByteCodeExprGen::VisitCompoundLiteralExpr( + const CompoundLiteralExpr *E) { + return materialize(E, E->getInitializer(), + /*isConst=*/E->getType().isConstQualified(), + /*isGlobal=*/E->isFileScope(), + /*isExtended=*/false); +} + +template +bool ByteCodeExprGen::VisitMaterializeTemporaryExpr( + const MaterializeTemporaryExpr *ME) { + const bool IsConst = ME->getType().isConstQualified(); + const bool IsGlobal = ME->getStorageDuration() == SD_Static; + const bool IsExtended = ME->getStorageDuration() == SD_Automatic; + return materialize(ME, ME->GetTemporaryExpr(), IsConst, IsGlobal, IsExtended); +} + +template +bool ByteCodeExprGen::materialize(const Expr *Alloc, const Expr *Init, + bool IsConst, bool IsGlobal, + bool IsExtended) { + if (IsGlobal) { + if (auto I = P.createGlobal(Alloc)) { + if (Optional T = classify(Init->getType())) { + // Primitive global - compute and set. + if (!visit(Init)) + return false; + if (!this->emitInitGlobal(*T, *I, Alloc)) + return false; + return DiscardResult ? true : this->emitGetPtrGlobal(*I, Alloc); + } else { + // Composite global - initialize in place. + if (!visitGlobalInitializer(Init, *I)) + return false; + return DiscardResult ? true : this->emitGetPtrGlobal(*I, Alloc); + } + } + } else { + if (Optional T = classify(Init->getType())) { + auto I = allocateLocalPrimitive(Init, *T, IsConst, IsExtended); + if (!visit(Init)) + return false; + if (!this->emitSetLocal(*T, I, Init)) + return false; + return DiscardResult ? true : this->emitGetPtrLocal(I, Init); + } else { + // Composite types - allocate storage and initialize it. + // This operation leaves a pointer to the temporary on the stack. + if (auto I = allocateLocal(Alloc, IsExtended)) { + if (!visitLocalInitializer(Init, *I)) + return false; + return DiscardResult ? true : this->emitGetPtrLocal(*I, Alloc); + } + } + } + return this->bail(Alloc); +} + +template +CharUnits ByteCodeExprGen::getAlignOfType(QualType T, + bool IsPreferred) { + // C++ [expr.alignof]p3: + // When alignof is applied to a reference type, the result is the + // alignment of the referenced type. + if (const ReferenceType *Ref = T->getAs()) + T = Ref->getPointeeType(); + + if (T.getQualifiers().hasUnaligned()) + return CharUnits::One(); + + const auto &AST = Ctx.getASTContext(); + const bool AlignOfReturnsPreferred = + AST.getLangOpts().getClangABICompat() <= LangOptions::ClangABI::Ver7; + + // __alignof is defined to return the preferred alignment. + // Before 8, clang returned the preferred alignment for alignof and _Alignof + // as well. + if (IsPreferred || AlignOfReturnsPreferred) + return AST.toCharUnitsFromBits(AST.getPreferredTypeAlign(T.getTypePtr())); + // alignof and _Alignof are defined to return the ABI alignment. + return AST.getTypeAlignInChars(T.getTypePtr()); +} + +template +CharUnits ByteCodeExprGen::getAlignOfExpr(const Expr *E, + bool IsPreferred) { + E = E->IgnoreParens(); + + // The kinds of expressions that we have special-case logic here for + // should be kept up to date with the special checks for those + // expressions in Sema. + + // alignof decl is always accepted, even if it doesn't make sense: we default + // to 1 in those cases. + if (const DeclRefExpr *DRE = dyn_cast(E)) + return Ctx.getASTContext().getDeclAlign(DRE->getDecl(), + /*RefAsPointee*/ true); + + if (const MemberExpr *ME = dyn_cast(E)) + return Ctx.getASTContext().getDeclAlign(ME->getMemberDecl(), + /*RefAsPointee*/ true); + + return getAlignOfType(E->getType(), IsPreferred); +} + +template +bool ByteCodeExprGen::VisitImplicitValueInitExpr( + const ImplicitValueInitExpr *E) { + + QualType Ty = E->getType(); + if (auto *AT = Ty->getAs()) + Ty = AT->getValueType(); + + if (auto T = Ctx.classify(Ty)) + return DiscardResult ? true : visitZeroInitializer(*T, E); + + if (auto *RT = Ty->getAs()) + return visitZeroInitializer(E, RT->getDecl()); + + if (auto *CAT = dyn_cast(Ty)) { + ImplicitValueInitExpr E(CAT->getElementType()); + return visitArrayInitializer(CAT, &E, [&E](unsigned) { return &E; }); + } + + return false; +} + +template +bool ByteCodeExprGen::VisitSubstNonTypeTemplateParmExpr( + const SubstNonTypeTemplateParmExpr *E) { + return this->Visit(E->getReplacement()); +} + +template +bool ByteCodeExprGen::VisitUnaryExprOrTypeTraitExpr( + const UnaryExprOrTypeTraitExpr *TE) { + switch (TE->getKind()) { + case UETT_PreferredAlignOf: + case UETT_AlignOf: { + const bool IsPreferred = TE->getKind() == UETT_PreferredAlignOf; + CharUnits Align; + if (TE->isArgumentType()) + Align = getAlignOfType(TE->getArgumentType(), IsPreferred); + else + Align = getAlignOfExpr(TE->getArgumentExpr(), IsPreferred); + return DiscardResult ? true : emitConst(TE, Align.getQuantity()); + } + + case UETT_VecStep: { + return this->bail(TE); + } + + case UETT_SizeOf: { + QualType ArgTy = TE->getTypeOfArgument(); + + // C++ [expr.sizeof]p2: "When applied to a reference or a reference type, + // the result is the size of the referenced type." + if (auto *Ref = ArgTy->getAs()) + ArgTy = Ref->getPointeeType(); + + CharUnits Size; + if (ArgTy->isVoidType() || ArgTy->isFunctionType()) { + Size = CharUnits::One(); + } else if (ArgTy->isDependentType()) { + return this->emitTrap(TE); + } else if (!ArgTy->isConstantSizeType()) { + // sizeof(vla) is not a constantexpr: C99 6.5.3.4p2. + // FIXME: Better diagnostic. + return this->emitTrap(TE); + } else { + Size = Ctx.getASTContext().getTypeSizeInChars(ArgTy); + } + + // Emit the size as an integer. + return DiscardResult ? true : emitConst(TE, Size.getQuantity()); + } + case UETT_OpenMPRequiredSimdAlign: { + return this->bail(TE); + } + } + + llvm_unreachable("unknown expr/type trait"); +} + +template +bool ByteCodeExprGen::VisitSizeOfPackExpr(const SizeOfPackExpr *E) { + if (DiscardResult) + return true; + return emitConst(E, E->getPackLength()); +} + +template +bool ByteCodeExprGen::VisitOpaqueValueExpr(const OpaqueValueExpr *E) { + // The opaque expression was evaluated earlier and the pointer was cached in + // a local variable. Load the pointer at this point. + PrimType Ty; + if (Optional T = classify(E->getType())) { + Ty = *T; + } else { + Ty = PT_Ptr; + } + auto It = OpaqueExprs.find(E); + if (It != OpaqueExprs.end()) { + return DiscardResult ? true : this->emitGetLocal(Ty, It->second, E); + } else { + return this->emitTrap(E); + } +} + +template +bool ByteCodeExprGen::VisitArrayInitLoopExpr( + const ArrayInitLoopExpr *E) { + // Evaluate the common expression, a pointer to the array copied from. + if (auto *C = E->getCommonExpr()) { + if (!visitOpaqueExpr(C)) + return false; + } + + // Initialise each element of the array. In this scope, ArrayIndex is set to + // refer to the index of the element being initialised in the callback which + // returns the initialiser of that element. + auto OldArrayIndex = ArrayIndex; + + auto ElemInit = [this, E](uint64_t I) { + ArrayIndex = I; + return E->getSubExpr(); + }; + + auto *AT = E->getType()->getAsArrayTypeUnsafe(); + if (!visitArrayInitializer(cast(AT), E, ElemInit)) + return false; + + ArrayIndex = OldArrayIndex; + return true; +} + +template +bool ByteCodeExprGen::VisitArrayInitIndexExpr( + const ArrayInitIndexExpr *E) { + assert(!DiscardResult && "ArrayInitIndexExpr should not be discarded"); + return ArrayIndex ? this->emitConst(E, *ArrayIndex) : this->emitTrap(E); +} + +template +bool ByteCodeExprGen::VisitInitListExpr(const InitListExpr *E) { + // Initialise a scalar with a given value or zero. + if (auto T = Ctx.classify(E->getType())) { + if (E->getNumInits() == 0) + return DiscardResult ? true : visitZeroInitializer(*T, E); + if (E->getNumInits() == 1) + return this->Visit(E->getInit(0)); + return false; + } + + // Desugar the type and decide which initializer to call based on it. + QualType Ty = E->getType(); + if (auto *AT = dyn_cast(Ty)) + Ty = AT->getValueType(); + + if (auto *RT = Ty->getAs()) + return visitRecordInitializer(RT, E); + + if (auto *CT = Ty->getAs()) + return visitComplexInitializer(CT, E); + + if (E->isStringLiteralInit()) { + auto *S = cast(E->getInit(0)->IgnoreParens()); + return visitStringInitializer(S); + } + + if (auto CT = Ty->getAsArrayTypeUnsafe()) { + if (auto CAT = dyn_cast(CT)) { + return visitArrayInitializer(CAT, E, [E](uint64_t I) { + if (I < E->getNumInits()) + return E->getInit(I); + else + return E->getArrayFiller(); + }); + } + } + + return this->bail(E); +} + +template +bool ByteCodeExprGen::VisitTypeTraitExpr(const TypeTraitExpr *E) { + return DiscardResult ? true : this->emitConstBool(E->getValue(), E); +} + +template +bool ByteCodeExprGen::VisitCXXNullPtrLiteralExpr( + const CXXNullPtrLiteralExpr *E) { + return DiscardResult ? true : this->emitNullPtr(E); +} + +template +bool ByteCodeExprGen::VisitCXXBoolLiteralExpr( + const CXXBoolLiteralExpr *B) { + return DiscardResult ? true : this->emitConstBool(B->getValue(), B); +} + +template +bool ByteCodeExprGen::VisitCXXThisExpr(const CXXThisExpr *TE) { + if (!this->emitThis(TE)) + return false; + return DiscardResult ? this->emitPopPtr(TE) : true; +} + +template +bool ByteCodeExprGen::VisitCXXDefaultArgExpr( + const CXXDefaultArgExpr *DE) { + return this->Visit(DE->getExpr()); +} + +template +bool ByteCodeExprGen::VisitCXXDefaultInitExpr( + const CXXDefaultInitExpr *DE) { + if (auto *E = DE->getExpr()) + return this->Visit(E); + return this->emitTrap(DE); +} + +template +bool ByteCodeExprGen::VisitCXXScalarValueInitExpr( + const CXXScalarValueInitExpr *E) { + QualType Ty = E->getType(); + if (auto T = Ctx.classify(Ty)) + return DiscardResult ? true : visitZeroInitializer(*T, E); + + // Complex numbers are not really scalar. + if (auto *CT = Ty->getAs()) { + QualType ElemType = CT->getElementType(); + PrimType T = classifyPrim(ElemType); + ImplicitValueInitExpr ZE(ElemType); + if (!emitInitFn()) + return false; + if (!visit(&ZE)) + return false; + if (!this->emitInitElem(T, 0, E)) + return false; + if (!visit(&ZE)) + return false; + return this->emitInitElemPop(T, 1, E); + } + return false; +} + +template +bool ByteCodeExprGen::VisitCXXThrowExpr(const CXXThrowExpr *E) { + return this->emitTrap(E); +} + +template +bool ByteCodeExprGen::VisitCXXTemporaryObjectExpr( + const CXXTemporaryObjectExpr *E) { + // In-place construction, simply invoke constructor. + if (InitFn) + return VisitCXXConstructExpr(cast(E)); + + // Allocate a temporary and build into it. + if (auto I = allocateLocal(E, /*isExtended=*/false)) { + OptionScope Scope(this, InitFnRef{[this, &I, E] { + return this->emitGetPtrLocal(*I, E); + }}); + if (!VisitCXXConstructExpr(cast(E))) + return false; + return DiscardResult ? true : this->emitGetPtrLocal(*I, E); + } + return this->bail(E); +} + +template +bool ByteCodeExprGen::VisitCXXTypeidExpr(const CXXTypeidExpr *E) { + // TODO: implement typeid. + return this->bail(E); +} + +template +bool ByteCodeExprGen::VisitCXXReinterpretCastExpr( + const CXXReinterpretCastExpr *E) { + if (!this->emitReinterpretCastWarning(E)) + return false; + return VisitCastExpr(E); +} + +template +bool ByteCodeExprGen::VisitCXXDynamicCastExpr( + const CXXDynamicCastExpr *E) { + if (!Ctx.getLangOpts().CPlusPlus2a) { + if (!this->emitDynamicCastWarning(E)) + return false; + } + return VisitCastExpr(E); +} + +template +bool ByteCodeExprGen::VisitCXXInheritedCtorInitExpr( + const CXXInheritedCtorInitExpr *E) { + auto *Ctor = E->getConstructor(); + + // Forward all parameters. + unsigned Offset = 0; + for (auto *PD : Ctor->parameters()) { + PrimType Ty; + if (Optional T = classify(PD->getType())) { + Ty = *T; + } else { + Ty = PT_Ptr; + } + if (!this->emitGetParam(Ty, Offset, E)) + return false; + Offset += align(primSize(Ty)); + } + + // Invoke the constructor on the same 'this'. + return emitInitFn() && emitMethodCall(Ctor, {}, E); +} + +template +bool ByteCodeExprGen::VisitCXXStdInitializerListExpr( + const CXXStdInitializerListExpr *E) { + auto *AT = getAsConstantArrayType(E->getSubExpr()->getType()); + + /// Push the pointer to the std::initializer_list. + if (!this->emitInitFn()) + return false; + + + Record *R = getRecord(E->getType()); + + // std::initializer_list should not have base classes. + if (!R || R->getNumBases() != 0 || R->getNumVirtualBases() != 0) + return this->emitTrap(E); + + // pointer + pointer or pointer + length + if (R->getNumFields() != 2) + return this->emitTrap(E); + + // The first field must be a pointer. + Record::Field *Fst = R->getField(0); + if (Fst->Desc->ElemTy != PT_Ptr) + return this->emitTrap(E); + + // Set the first field - either a pointer or an integer. + Record::Field *Snd = R->getField(1); + if (Optional T = Snd->Desc->ElemTy) { + QualType Ty = Snd->Decl->getType(); + switch (*T) { + case PT_Sint8: + case PT_Uint8: + case PT_Sint16: + case PT_Uint16: + case PT_Sint32: + case PT_Uint32: + case PT_Sint64: + case PT_Uint64: + case PT_SintFP: + case PT_UintFP: + case PT_Bool: + /// Lower the array. + if (!visit(E->getSubExpr())) + return false; + // Set the first field. + if (!this->emitInitFieldPtr(Fst->Offset, E)) + return false; + // Set the length. + if (!this->emitConst(*T, getIntWidth(Ty), AT->getSize(), E)) + return false; + if (DiscardResult) + return this->emitInitFieldPop(*T, Snd->Offset, E); + else + return this->emitInitField(*T, Snd->Offset, E); + case PT_Ptr: + /// Lower the array. + if (!visit(E->getSubExpr())) + return false; + if (!this->emitInitFieldPeekPtr(Fst->Offset, E)) + return false; + // Set the end pointer. + if (!this->emitConstUint64(AT->getSize().getZExtValue(), E)) + return false; + if (!this->emitAddOffsetUint64(E)) + return false; + if (DiscardResult) + return this->emitInitFieldPopPtr(Snd->Offset, E); + else + return this->emitInitFieldPtr(Snd->Offset, E); + default: + return this->emitTrap(E); + } + } + return this->emitTrap(E); +} + +template +bool ByteCodeExprGen::discard(const Expr *E) { + OptionScope Scope(this, /*discardResult=*/true); + return this->Visit(E); +} + +template +bool ByteCodeExprGen::visit(const Expr *E) { + OptionScope Scope(this, /*discardResult=*/false); + return this->Visit(E); +} + +template +bool ByteCodeExprGen::visitBool(const Expr *E) { + if (Optional T = classify(E->getType())) { + if (!visit(E)) + return false; + return (*T != PT_Bool) ? this->emitTest(*T, E) : true; + } else { + return this->bail(E); + } +} + +template +bool ByteCodeExprGen::visitZeroInitializer(PrimType T, const Expr *E) { + switch (T) { + case PT_Bool: + return this->emitZeroBool(E); + case PT_Sint8: + return this->emitZeroSint8(E); + case PT_Uint8: + return this->emitZeroUint8(E); + case PT_Sint16: + return this->emitZeroSint16(E); + case PT_Uint16: + return this->emitZeroUint16(E); + case PT_Sint32: + return this->emitZeroSint32(E); + case PT_Uint32: + return this->emitZeroUint32(E); + case PT_Sint64: + return this->emitZeroSint64(E); + case PT_Uint64: + return this->emitZeroUint64(E); + case PT_UintFP: + return this->emitZeroFPUintFP(getIntWidth(E->getType()), E); + case PT_SintFP: + return this->emitZeroFPSintFP(getIntWidth(E->getType()), E); + case PT_RealFP: + return this->emitZeroRealFP(getFltSemantics(E->getType()), E); + case PT_Ptr: + return this->emitNullPtr(E); + case PT_FnPtr: + return this->emitNullFnPtr(E); + case PT_MemPtr: + return this->emitNullMemPtr(E); + } +} + +template +bool ByteCodeExprGen::visitOffset(const Expr *Ptr, const Expr *Offset, + const Expr *E, UnaryFn OffsetFn) { + if (!visit(Ptr)) + return false; + if (!visit(Offset)) + return false; + if (!(this->*OffsetFn)(*classify(Offset->getType()), E)) + return false; + return DiscardResult ? this->emitPopPtr(E) : true; +} + +template +bool ByteCodeExprGen::visitIndirectMember(const BinaryOperator *E) { + if (!visit(E->getLHS())) + return false; + if (!visit(E->getRHS())) + return false; + + if (!this->emitGetPtrFieldIndirect(E)) + return false; + if (DiscardResult && !this->emitPopPtr(E)) + return false; + return true; +} + +template +bool ByteCodeExprGen::visitAssign(PrimType T, + const BinaryOperator *BO) { + return dereference( + BO->getLHS(), DerefKind::Write, + [this, BO](PrimType) { + // Generate a value to store - will be set. + return visit(BO->getRHS()); + }, + [this, BO](PrimType T) { + // Pointer on stack - compile RHS and assign to pointer. + if (!visit(BO->getRHS())) + return false; + + if (BO->getLHS()->refersToBitField()) { + if (DiscardResult) + return this->emitStoreBitFieldPop(T, BO); + else + return this->emitStoreBitField(T, BO); + } else { + if (DiscardResult) + return this->emitStorePop(T, BO); + else + return this->emitStore(T, BO); + } + }); +} + +template +bool ByteCodeExprGen::visitShiftAssign(PrimType RHS, BinaryFn F, + const BinaryOperator *BO) { + return dereference( + BO->getLHS(), DerefKind::ReadWrite, + [this, F, RHS, BO](PrimType LHS) { + if (!visit(BO->getRHS())) + return false; + (this->*F)(LHS, RHS, BO); + return true; + }, + [this, F, RHS, BO](PrimType LHS) { + if (!this->emitLoad(LHS, BO)) + return false; + if (!visit(BO->getRHS())) + return false; + if (!(this->*F)(LHS, RHS, BO)) + return false; + + if (BO->getLHS()->refersToBitField()) { + if (DiscardResult) + return this->emitStoreBitFieldPop(LHS, BO); + else + return this->emitStoreBitField(LHS, BO); + } else { + if (DiscardResult) + return this->emitStorePop(LHS, BO); + else + return this->emitStore(LHS, BO); + } + }); +} + +template +bool ByteCodeExprGen::visitCompoundAssign(PrimType RHS, UnaryFn F, + const BinaryOperator *BO) { + auto ApplyOperation = [this, F, BO, RHS](PrimType LHS) { + auto *ExprRHS = BO->getRHS(); + auto *ExprLHS = BO->getLHS(); + if (ExprLHS->getType() == ExprRHS->getType()) { + if (!visit(BO->getRHS())) + return false; + if (!(this->*F)(LHS, BO)) + return false; + } else { + if (!emitConv(LHS, ExprLHS->getType(), RHS, ExprRHS->getType(), ExprRHS)) + return false; + if (!visit(ExprRHS)) + return false; + if (!(this->*F)(RHS, BO)) + return false; + if (!emitConv(RHS, ExprRHS->getType(), LHS, ExprLHS->getType(), ExprLHS)) + return false; + } + return true; + }; + + return dereference( + BO->getLHS(), DerefKind::ReadWrite, ApplyOperation, + [this, BO, &ApplyOperation](PrimType LHS) -> bool { + if (!this->emitLoad(LHS, BO)) + return false; + if (!ApplyOperation(LHS)) + return false; + + if (BO->getLHS()->refersToBitField()) { + if (DiscardResult) + return this->emitStoreBitFieldPop(LHS, BO); + else + return this->emitStoreBitField(LHS, BO); + } else { + if (DiscardResult) + return this->emitStorePop(LHS, BO); + else + return this->emitStore(LHS, BO); + } + }); +} + +template +bool ByteCodeExprGen::visitPtrAssign(PrimType RHS, UnaryFn F, + const BinaryOperator *BO) { + return dereference( + BO->getLHS(), DerefKind::ReadWrite, + [this, F, BO, RHS](PrimType LHS) { + if (!visit(BO->getRHS())) + return false; + if (!(this->*F)(RHS, BO)) + return false; + return true; + }, + [this, BO, F, RHS](PrimType LHS) -> bool { + if (!this->emitLoad(LHS, BO)) + return false; + if (!visit(BO->getRHS())) + return false; + if (!(this->*F)(RHS, BO)) + return false; + + if (BO->getLHS()->refersToBitField()) + return this->bail(BO); + + if (DiscardResult) + return this->emitStorePop(LHS, BO); + else + return this->emitStore(LHS, BO); + }); +} + +template +bool ByteCodeExprGen::emitConv(PrimType LHS, QualType TyLHS, + PrimType RHS, QualType TyRHS, + const Expr *Cast) { + if (isPrimitiveIntegral(RHS)) { + if (isFixedReal(LHS)) { + return this->emitCastRealFPToAlu(LHS, RHS, Cast); + } else { + return this->emitCast(LHS, RHS, Cast); + } + } else if (isFixedIntegral(RHS)) { + if (isFixedReal(LHS)) { + return this->emitCastRealFPToAluFP(LHS, RHS, getIntWidth(TyRHS), Cast); + } else { + return this->emitCastFP(LHS, RHS, getIntWidth(TyRHS), Cast); + } + } else if (isFixedReal(RHS)) { + return this->emitCastRealFP(LHS, getFltSemantics(TyRHS), Cast); + } + llvm_unreachable("Invalid conversion"); +} + +template +bool ByteCodeExprGen::visitShortCircuit(const BinaryOperator *E) { + if (!visitBool(E->getLHS())) + return false; + + LabelTy Short = this->getLabel(); + const bool IsTrue = E->getOpcode() == BO_LAnd; + if (DiscardResult) { + if (!(IsTrue ? this->jumpFalse(Short) : this->jumpTrue(Short))) + return false; + if (!this->discard(E->getRHS())) + return false; + } else { + if (!this->emitDupBool(E)) + return false; + if (!(IsTrue ? this->jumpFalse(Short) : this->jumpTrue(Short))) + return false; + if (!this->emitPopBool(E)) + return false; + if (!visitBool(E->getRHS())) + return false; + } + this->fallthrough(Short); + return true; +} + +template +bool ByteCodeExprGen::dereference( + const Expr *LV, DerefKind AK, llvm::function_ref Direct, + llvm::function_ref Indirect) { + if (Optional T = classify(LV->getType())) { + if (!LV->refersToBitField()) { + // Only primitive, non bit-field types can be dereferenced directly. + if (auto *DE = dyn_cast(LV)) { + if (!DE->getDecl()->getType()->isReferenceType()) { + if (auto *PD = dyn_cast(DE->getDecl())) + return dereferenceParam(LV, *T, PD, AK, Direct, Indirect); + if (auto *VD = dyn_cast(DE->getDecl())) + return dereferenceVar(LV, *T, VD, AK, Direct, Indirect); + } + } + if (auto *ME = dyn_cast(LV)) { + if (!ME->getMemberDecl()->getType()->isReferenceType()) + return dereferenceMember(ME, *T, AK, Direct, Indirect); + } + } + + if (!visit(LV)) + return false; + return Indirect(*T); + } + + return false; +} + +template +bool ByteCodeExprGen::dereferenceParam( + const Expr *LV, PrimType T, const ParmVarDecl *PD, DerefKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect) { + auto It = this->Params.find(PD); + if (It != this->Params.end()) { + unsigned Idx = It->second; + switch (AK) { + case DerefKind::Read: + return DiscardResult ? true : this->emitGetParam(T, Idx, LV); + + case DerefKind::Write: + if (!Direct(T)) + return false; + if (!this->emitSetParam(T, Idx, LV)) + return false; + return DiscardResult ? true : this->emitGetPtrParam(Idx, LV); + + case DerefKind::ReadWrite: + if (!this->emitGetParam(T, Idx, LV)) + return false; + if (!Direct(T)) + return false; + if (!this->emitSetParam(T, Idx, LV)) + return false; + return DiscardResult ? true : this->emitGetPtrParam(Idx, LV); + } + return true; + } + + // If the param is a pointer, we can dereference a dummy value. + if (!DiscardResult && T == PT_Ptr && AK == DerefKind::Read) { + if (auto Idx = P.getOrCreateDummy(PD)) + return this->emitGetPtrGlobal(*Idx, PD); + return false; + } + + // Value cannot be produced - try to emit pointer and do stuff with it. + return visit(LV) && Indirect(T); +} + +template +bool ByteCodeExprGen::dereferenceVar( + const Expr *LV, PrimType T, const VarDecl *VD, DerefKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect) { + auto It = Locals.find(VD); + if (It != Locals.end()) { + const auto &L = It->second; + switch (AK) { + case DerefKind::Read: + if (!this->emitGetLocal(T, L.Offset, LV)) + return false; + return DiscardResult ? this->emitPop(T, LV) : true; + + case DerefKind::Write: + if (!Direct(T)) + return false; + if (!this->emitSetLocal(T, L.Offset, LV)) + return false; + return DiscardResult ? true : this->emitGetPtrLocal(L.Offset, LV); + + case DerefKind::ReadWrite: + if (!this->emitGetLocal(T, L.Offset, LV)) + return false; + if (!Direct(T)) + return false; + if (!this->emitSetLocal(T, L.Offset, LV)) + return false; + return DiscardResult ? true : this->emitGetPtrLocal(L.Offset, LV); + } + } else if (auto Idx = getGlobalIdx(VD)) { + switch (AK) { + case DerefKind::Read: + if (!this->emitGetGlobal(T, *Idx, LV)) + return false; + return DiscardResult ? this->emitPop(T, LV) : true; + + case DerefKind::Write: + if (!Direct(T)) + return false; + if (!this->emitSetGlobal(T, *Idx, LV)) + return false; + return DiscardResult ? true : this->emitGetPtrGlobal(*Idx, LV); + + case DerefKind::ReadWrite: + if (!this->emitGetGlobal(T, *Idx, LV)) + return false; + if (!Direct(T)) + return false; + if (!this->emitSetGlobal(T, *Idx, LV)) + return false; + return DiscardResult ? true : this->emitGetPtrGlobal(*Idx, LV); + } + } + + // 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 (!DiscardResult && AK == DerefKind::Read) { + if (VD->hasLocalStorage() && VD->hasInit() && !VD->isConstexpr()) { + QualType VT = VD->getType(); + if (VT.isConstQualified() && VT->isFundamentalType()) + return this->Visit(VD->getInit()); + } + } + + // Value cannot be produced - try to emit pointer. + return visit(LV) && Indirect(T); +} + +template +bool ByteCodeExprGen::dereferenceMember( + const MemberExpr *ME, PrimType T, DerefKind AK, + llvm::function_ref Direct, + llvm::function_ref Indirect) { + // Fetch or read the required field. + if (auto *FD = dyn_cast(ME->getMemberDecl())) { + return withField(FD, [this, ME, AK, T, Direct](const Record::Field *F) { + const unsigned Off = F->Offset; + if (isa(ME->getBase())) { + switch (AK) { + case DerefKind::Read: + if (!this->emitGetThisField(T, Off, ME)) + return false; + return DiscardResult ? this->emitPop(T, ME) : true; + + case DerefKind::Write: + if (!Direct(T)) + return false; + if (!this->emitSetThisField(T, Off, ME)) + return false; + return DiscardResult ? true : this->emitGetPtrThisField(Off, ME); + + case DerefKind::ReadWrite: + if (!this->emitGetThisField(T, Off, ME)) + return false; + if (!Direct(T)) + return false; + if (!this->emitSetThisField(T, Off, ME)) + return false; + return DiscardResult ? true : this->emitGetPtrThisField(Off, ME); + } + } else { + if (!visit(ME->getBase())) + return false; + + switch (AK) { + case DerefKind::Read: + if (!this->emitGetFieldPop(T, Off, ME)) + return false; + return DiscardResult ? this->emitPop(T, ME) : true; + + case DerefKind::Write: + if (!Direct(T)) + return false; + if (!this->emitSetField(T, Off, ME)) + return false; + return DiscardResult ? true : this->emitGetPtrField(Off, ME); + + case DerefKind::ReadWrite: + if (!this->emitGetField(T, Off, ME)) + return false; + if (!Direct(T)) + return false; + if (!this->emitSetField(T, Off, ME)) + return false; + return DiscardResult ? true : this->emitGetPtrField(Off, ME); + } + } + }); + } + + // Value cannot be produced - try to emit pointer. + return visit(ME) && Indirect(T); +} + +template +bool ByteCodeExprGen::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_SintFP: + return this->emitConstFPSintFP(NumBits, Value.getSExtValue(), E); + case PT_UintFP: + return this->emitConstFPUintFP(NumBits, Value.getZExtValue(), E); + case PT_Bool: + return this->emitConstBool(Value.getBoolValue(), E); + case PT_Ptr: + case PT_FnPtr: + case PT_RealFP: + case PT_MemPtr: + llvm_unreachable("Invalid integral type"); + break; + } +} + +template +unsigned ByteCodeExprGen::allocateLocalPrimitive(DeclTy &&Src, + PrimType Ty, + bool IsConst, + bool IsExtended) { + Descriptor *D = P.createDescriptor(Src, Ty, IsConst, Src.is()); + Scope::Local Local = this->createLocal(D); + if (auto *VD = dyn_cast_or_null(Src.dyn_cast())) + Locals.insert({VD, Local}); + VarScope->add(Local, IsExtended); + return Local.Offset; +} + +template +llvm::Optional +ByteCodeExprGen::allocateLocal(DeclTy &&Src, bool IsExtended) { + QualType Ty; + + const ValueDecl *Key = nullptr; + bool IsTemporary = false; + if (auto *VD = dyn_cast_or_null(Src.dyn_cast())) { + Key = VD; + Ty = VD->getType(); + } + if (auto *E = Src.dyn_cast()) { + IsTemporary = true; + Ty = E->getType(); + } + + Descriptor *D = P.createDescriptor(Src, Ty.getTypePtr(), + Ty.isConstQualified(), IsTemporary); + if (!D) + return {}; + + Scope::Local Local = this->createLocal(D); + if (Key) + Locals.insert({Key, Local}); + VarScope->add(Local, IsExtended); + return Local.Offset; +} + +template +bool ByteCodeExprGen::visitArguments(QualType CalleeTy, + ArrayRef Args) { + if (auto *MemberTy = CalleeTy->getAs()) + CalleeTy = MemberTy->getPointeeType(); + if (auto *PtrTy = CalleeTy->getAs()) + CalleeTy = PtrTy->getPointeeType(); + + auto *FnTy = CalleeTy->getAs(); + assert(FnTy && "not a function proto type"); + + for (unsigned I = 0, N = Args.size(); I < N; ++I) { + if (!visitArgument(Args[I], I >= FnTy->getNumParams())) + return false; + } + return true; +} + +template +bool ByteCodeExprGen::visitArgument(const Expr *E, bool Discard) { + // Primitive or pointer argument - leave it on the stack. + if (Optional T = classify(E)) + return Discard ? discard(E) : visit(E); + + // Composite argument - copy construct and push pointer. + if (auto I = allocateLocal(E, /*isExtended=*/false)) { + if (!visitLocalInitializer(E, *I)) + return false; + return Discard ? true : this->emitGetPtrLocal(*I, E); + } + + return this->bail(E); +} + +template +bool ByteCodeExprGen::visitInitializer( + const Expr *Init, InitFnRef InitFn) { + OptionScope Scope(this, InitFn); + return this->Visit(Init); +} + +template +bool ByteCodeExprGen::visitBaseInitializer(const Expr *Init, + InitFnRef GenBase) { + OptionScope Scope(this, GenBase, InitKind::BASE); + return this->Visit(Init); +} + +template +bool ByteCodeExprGen::getPtrConstFn(const FunctionDecl *FD, + const Expr *E) { + if (Expected Func = P.getOrCreateFunction(FD)) { + if (*Func) + return this->emitConstFn(*Func, E); + else + return this->emitConstNoFn(FD, E); + } else { + consumeError(Func.takeError()); + return this->emitConstNoFn(FD, E); + } +} + +template +bool ByteCodeExprGen::getPtrVarDecl(const VarDecl *VD, const Expr *E) { + // Generate a pointer to the local, loading refs. + if (Optional Idx = getGlobalIdx(VD)) { + if (VD->getType()->isReferenceType()) + return this->emitGetGlobalPtr(*Idx, E); + else + return this->emitGetPtrGlobal(*Idx, E); + } + return false; +} + +template +llvm::Optional +ByteCodeExprGen::getGlobalIdx(const VarDecl *VD) { + if (VD->isConstexpr()) { + // Constexpr decl - it must have already been defined. + return P.getGlobal(VD); + } + if (!VD->hasLocalStorage()) { + // Not constexpr, but a global var - can have pointer taken. + Program::DeclScope Scope(P, VD); + return P.getOrCreateGlobal(VD); + } + return {}; +} + +template +bool ByteCodeExprGen::visitStringInitializer(const StringLiteral *S) { + // Find the type to represent characters. + const unsigned CharBytes = S->getCharByteWidth(); + PrimType CharType; + switch (CharBytes) { + case 1: + CharType = PT_Sint8; + break; + case 2: + CharType = PT_Uint16; + break; + case 4: + CharType = PT_Uint32; + break; + default: + llvm_unreachable("Unsupported character width!"); + } + + if (!emitInitFn()) + return false; + + // Initialise elements one by one, advancing the pointer. + const unsigned NumBits = CharBytes * getCharBit(); + for (unsigned I = 0, N = S->getLength(); I < N; ++I) { + // Set individual characters here. + APInt CodeUnit(NumBits, S->getCodeUnit(I)); + // Lower the code point. + if (!emitConst(CharType, NumBits, CodeUnit, S)) + return false; + // Set the character. + if (!this->emitInitElem(CharType, I, S)) + return false; + } + + // Set the null terminator. + if (!emitConst(CharType, NumBits, APInt(NumBits, 0), S)) + return false; + if (!this->emitInitElemPop(CharType, S->getLength(), S)) + return false; + + // String was initialised. + return true; +} + +template +bool ByteCodeExprGen::visitRecordInitializer( + const RecordType *RT, const InitListExpr *List) { + auto *R = P.getOrCreateRecord(RT->getDecl()); + if (!R) + return this->bail(List); + + auto InitElem = [this, R](const Record::Field *F, const Expr *E) { + if (Optional T = classify(E)) { + if (!emitInitFn()) + return false; + if (!visit(E)) + return false; + if (R->isUnion()) + return this->emitInitFieldActive(*T, F->Offset, E); + else if (F->Decl->isBitField()) + return this->emitInitBitField(*T, F, E); + else + return this->emitInitFieldPop(*T, F->Offset, E); + } else { + auto FieldFn = [this, F, E](InitFnRef Ptr) { + return Ptr() && this->emitGetPtrField(F->Offset, E); + }; + if (R->isUnion()) { + UnionScope Scope(this, FieldFn); + return this->Visit(E); + } else { + FieldScope Scope(this, FieldFn); + return this->Visit(E); + } + } + }; + + if (R->isUnion()) { + if (auto *InitField = List->getInitializedFieldInUnion()) { + auto *F = R->getField(InitField); + switch (List->getNumInits()) { + case 0: { + // Clang doesn't provide an initializer - need to default init. + ImplicitValueInitExpr Init(InitField->getType()); + if (!InitElem(F, &Init)) + return false; + break; + } + + case 1: { + // Initialise the element. + if (!InitElem(F, List->getInit(0))) + return false; + break; + } + + default: + // Malformed initializer. + return false; + } + } + } else { + for (unsigned I = 0, N = R->getNumBases(); I < N; ++I) { + unsigned Off = R->getBase(I)->Offset; + const Expr *Init = List->getInit(I); + + BaseScope Scope(this, [this, Off, Init] (InitFnRef Ptr) { + return Ptr() && this->emitGetPtrBase(Off, Init); + }); + if (!this->Visit(Init)) + return false; + } + for (unsigned I = 0, N = R->getNumFields(); I < N; ++I) { + const Expr * Init = List->getInit(I + R->getNumBases()); + if (!InitElem(R->getField(I), Init)) + return false; + } + } + + switch (Initialiser) { + case InitKind::ROOT: + // Nothing to initialise. + return true; + case InitKind::BASE: + // Initialise the base class. + return this->emitInitFn() && this->emitInitialise(List); + case InitKind::UNION: + // Activate the union field. + return this->emitInitFn() && this->emitActivate(List); + } +} + + +template +bool ByteCodeExprGen::visitComplexInitializer( + const ComplexType *CT, const InitListExpr *List) { + QualType ElemTy = CT->getElementType(); + + ImplicitValueInitExpr ZE(ElemTy); + PrimType T = classifyPrim(ElemTy); + + auto InitElem = [this, T](unsigned Index, const Expr *E) -> bool { + if (!emitInitFn()) + return false; + if (!visit(E)) + return false; + return this->emitInitElemPop(T, Index, E); + }; + + switch (List->getNumInits()) { + case 0: + return InitElem(0, &ZE) && InitElem(1, &ZE); + case 1: + return this->Visit(List->getInit(0)); + case 2: + return InitElem(0, List->getInit(0)) && InitElem(1, List->getInit(1)); + default: + llvm_unreachable("invalid complex initializer"); + } +} + +template +bool ByteCodeExprGen::visitCastToComplex(const CastExpr *CE) { + QualType SubType = CE->getSubExpr()->getType(); + PrimType T = classifyPrim(SubType); + + if (!emitInitFn()) + return false; + if (!this->visit(CE->getSubExpr())) + return false; + if (!this->emitInitElem(T, 0, CE)) + return false; + ImplicitValueInitExpr ZE(SubType); + if (!visit(&ZE)) + return false; + return this->emitInitElemPop(T, 1, CE); +} + +template +bool ByteCodeExprGen::visitArrayInitializer( + const ConstantArrayType *AT, + const Expr *List, + llvm::function_ref Elem) { + uint64_t NumElems = AT->getSize().getZExtValue(); + if (Optional T = classify(AT->getElementType())) { + if (NumElems > 0 && !emitInitFn()) + return false; + for (unsigned I = 0; I < NumElems; ++I) { + const Expr *ElemInit = Elem(I); + // Construct the value. + if (!visit(ElemInit)) + return false; + // Set the element. + if (I + 1 != NumElems) { + if (!this->emitInitElem(*T, I, ElemInit)) + return false; + } else { + if (!this->emitInitElemPop(*T, I, ElemInit)) + return false; + } + } + } else { + for (unsigned I = 0; I < NumElems; ++I) { + const Expr *ElemInit = Elem(I); + + // Generate a pointer to the field from the array pointer. + FieldScope Scope(this, [this, I, ElemInit](InitFnRef Ptr) { + if (!Ptr()) + return false; + if (!this->emitConstUint32(I, ElemInit)) + return false; + if (!this->emitAddOffsetUint32(ElemInit)) + return false; + return this->emitNarrowPtr(ElemInit); + }); + if (!this->Visit(ElemInit)) + return false; + } + } + + switch (Initialiser) { + case InitKind::ROOT: + return true; + case InitKind::BASE: + llvm_unreachable("arrays cannot be base classes"); + case InitKind::UNION: + return this->emitInitFn() && this->emitActivate(List); + } +} + +template +bool ByteCodeExprGen::visitZeroInitializer(const Expr *E, + const RecordDecl *RD) { + Record *R = P.getOrCreateRecord(RD); + if (!R) + return false; + + for (auto &B : R->bases()) { + BaseScope Scope(this, [this, &B, E](InitFnRef Ptr) { + if (!Ptr()) + return false; + return this->emitGetPtrBase(B.Offset, E); + }); + if (!visitZeroInitializer(E, B.Decl)) + return false; + } + + for (auto &F : R->fields()) { + ImplicitValueInitExpr Init(F.Decl->getType()); + if (Optional T = classify(F.Decl->getType())) { + if (!emitInitFn()) + return false; + if (!visitZeroInitializer(*T, &Init)) + return false; + if (F.Decl->isBitField()) { + if (!this->emitInitBitField(*T, &F, E)) + return false; + } else { + if (!this->emitInitFieldPop(*T, F.Offset, E)) + return false; + } + } else { + FieldScope Scope(this, [this, &F, E](InitFnRef Ptr) { + if (!Ptr()) + return false; + return this->emitGetPtrField(F.Offset, E); + }); + if (!this->Visit(&Init)) + return false; + } + } + return true; +} + +template +bool ByteCodeExprGen::withField( + const FieldDecl *F, + llvm::function_ref GenField) { + if (auto *R = getRecord(F->getParent())) + if (auto *Field = R->getField(F)) + return GenField(Field); + return false; +} + +template +const RecordType *ByteCodeExprGen::getRecordTy(QualType Ty) { + if (auto *PT = dyn_cast(Ty)) + return PT->getPointeeType()->getAs(); + else + return Ty->getAs(); +} + +template +Record *ByteCodeExprGen::getRecord(QualType Ty) { + if (auto *RecordTy = getRecordTy(Ty)) { + return getRecord(RecordTy->getDecl()); + } + return nullptr; +} + +template +Record *ByteCodeExprGen::getRecord(const RecordDecl *RD) { + return P.getOrCreateRecord(RD); +} + +template +bool ByteCodeExprGen::visitOpaqueExpr(const OpaqueValueExpr *E) { + PrimType Ty; + if (Optional T = classify(E->getType())) { + Ty = *T; + } else { + Ty = PT_Ptr; + } + + auto Off = allocateLocalPrimitive(E, Ty, /*isConst=*/true); + if (!visit(E->getSourceExpr())) + return false; + this->emitSetLocal(Ty, Off, E); + OpaqueExprs.insert({E, Off}); + return true; +} + +template +bool ByteCodeExprGen::visitExpr(const Expr *Exp) { + ExprScope RootScope(this); + if (!visit(Exp)) + return false; + + if (Optional T = classify(Exp)) + return this->emitRet(*T, Exp); + else + return this->emitRetValue(Exp); +} + +template +bool ByteCodeExprGen::visitDecl(const VarDecl *VD) { + const Expr *Init = VD->getInit(); + + if (Optional I = P.createGlobal(VD)) { + if (Optional T = classify(VD->getType())) { + { + // Primitive declarations - compute the value and set it. + DeclScope LocalScope(this, VD); + if (!visit(Init)) + return false; + } + + // If the declaration is global, save the value for later use. + 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. + DeclScope LocalScope(this, VD); + if (!visitGlobalInitializer(Init, *I)) + return false; + } + + // Return a pointer to the global. + if (!this->emitGetPtrGlobal(*I, VD)) + return false; + return this->emitRetValue(VD); + } + } + + return this->bail(VD); +} + +template +void ByteCodeExprGen::emitCleanup() { + for (VariableScope *C = VarScope; C; C = C->getParent()) + C->emitDestruction(); +} + +namespace clang { +namespace interp { + +template class ByteCodeExprGen; +template class ByteCodeExprGen; + +} // 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/ByteCodeStmtGen.h b/clang/lib/AST/Interp/ByteCodeStmtGen.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeStmtGen.h @@ -0,0 +1,103 @@ +//===--- ByteCodeStmtGen.h - Code generator for expressions -----*- 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_BYTECODESTMTGEN_H +#define LLVM_CLANG_AST_INTERP_BYTECODESTMTGEN_H + +#include "ByteCodeExprGen.h" +#include "ByteCodeEmitter.h" +#include "EvalEmitter.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 LoopScope; +template class SwitchScope; +template class LabelScope; + +/// Compilation context for statements. +template +class ByteCodeStmtGen : public ByteCodeExprGen { + using LabelTy = typename Emitter::LabelTy; + using AddrTy = typename Emitter::AddrTy; + using OptLabelTy = llvm::Optional; + using CaseMap = llvm::DenseMap; + +public: + template + ByteCodeStmtGen(Tys&&... Args) + : ByteCodeExprGen(std::forward(Args)...) {} + +protected: + bool visitFunc(const FunctionDecl *F) override; + +private: + friend class LabelScope; + friend class LoopScope; + friend class SwitchScope; + + // Statement visitors. + bool visitStmt(const Stmt *S); + bool visitCompoundStmt(const CompoundStmt *S); + bool visitDeclStmt(const DeclStmt *DS); + bool visitForStmt(const ForStmt *FS); + bool visitWhileStmt(const WhileStmt *DS); + bool visitDoStmt(const DoStmt *DS); + bool visitReturnStmt(const ReturnStmt *RS); + bool visitIfStmt(const IfStmt *IS); + bool visitBreakStmt(const BreakStmt *BS); + bool visitContinueStmt(const ContinueStmt *CS); + bool visitSwitchStmt(const SwitchStmt *SS); + bool visitCaseStmt(const SwitchCase *CS); + bool visitCXXForRangeStmt(const CXXForRangeStmt *FS); + + /// Compiles a variable declaration. + bool visitVarDecl(const VarDecl *VD); + + /// Visits a field initializer. + bool visitCtorInit(Record *This, const CXXCtorInitializer *Init); + +private: + /// Type of the expression returned by the function. + llvm::Optional ReturnType; + + /// Current scope. + LabelScope *LabelScope = nullptr; + + /// 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 ByteCodeExprGen; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/ByteCodeStmtGen.cpp b/clang/lib/AST/Interp/ByteCodeStmtGen.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeStmtGen.cpp @@ -0,0 +1,683 @@ +//===--- ByteCodeStmtGen.cpp - Code generator for expressions ---*- 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 "ByteCodeStmtGen.h" +#include "ByteCodeEmitter.h" +#include "ByteCodeGenError.h" +#include "Context.h" +#include "Function.h" +#include "Program.h" +#include "State.h" +#include "Type.h" + +using namespace clang; +using namespace clang::interp; + +template using Expected = llvm::Expected; +template using Optional = llvm::Optional; + +namespace clang { +namespace interp { + +/// Scope managing label targets. +template class LabelScope { +public: + virtual ~LabelScope() { Ctx->LabelScope = this->Parent; } + + LabelScope *getParent() { return Parent; } + +protected: + LabelScope(ByteCodeStmtGen *Ctx) + : Ctx(Ctx), Parent(Ctx->LabelScope) { + Ctx->LabelScope = this; + } + + /// ByteCodeStmtGen instance. + ByteCodeStmtGen *Ctx; + /// Link to the parent scope. + LabelScope *Parent; +}; + +/// Sets the context for break/continue statements. +template class LoopScope final : public LabelScope { +public: + using LabelTy = typename ByteCodeStmtGen::LabelTy; + using OptLabelTy = typename ByteCodeStmtGen::OptLabelTy; + + LoopScope(ByteCodeStmtGen *Ctx, LabelTy BreakLabel, + LabelTy ContinueLabel) + : LabelScope(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 LabelScope { +public: + using LabelTy = typename ByteCodeStmtGen::LabelTy; + using OptLabelTy = typename ByteCodeStmtGen::OptLabelTy; + using CaseMap = typename ByteCodeStmtGen::CaseMap; + + SwitchScope(ByteCodeStmtGen *Ctx, CaseMap &&CaseLabels, + LabelTy BreakLabel, OptLabelTy DefaultLabel) + : LabelScope(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 ByteCodeStmtGen::visitFunc(const FunctionDecl *F) { + // Classify the return type. + ReturnType = this->classify(F->getReturnType()); + + // Set up fields and context if a constructor. + if (auto *MD = dyn_cast(F)) { + const CXXRecordDecl *RD = MD->getParent()->getCanonicalDecl(); + if (auto *R = this->getRecord(RD)) { + if (auto *CD = dyn_cast(MD)) { + // If this is a copy or move constructor for a union, emit a special + // opcode since the operation cannot be represented in the AST easily. + if (CD->isDefaulted() && CD->isCopyOrMoveConstructor() && RD->isUnion()) + return this->emitInitUnion(CD) && this->emitRetVoid(CD); + + if (CD->isDelegatingConstructor()) { + CXXConstructorDecl::init_const_iterator I = CD->init_begin(); + { + ExprScope InitScope(this); + if (!this->visitThisInitializer((*I)->getInit())) + return false; + } + } else { + // Compile all member initializers. + for (const CXXCtorInitializer *Init : CD->inits()) { + if (!visitCtorInit(R, Init)) + return false; + } + } + } + } else { + return this->bail(RD); + } + } + + if (auto *Body = F->getBody()) + if (!visitStmt(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 ByteCodeStmtGen::visitStmt(const Stmt *S) { + switch (S->getStmtClass()) { + case Stmt::CompoundStmtClass: + return visitCompoundStmt(cast(S)); + case Stmt::DeclStmtClass: + return visitDeclStmt(cast(S)); + case Stmt::ForStmtClass: + return visitForStmt(cast(S)); + case Stmt::WhileStmtClass: + return visitWhileStmt(cast(S)); + case Stmt::DoStmtClass: + return visitDoStmt(cast(S)); + case Stmt::ReturnStmtClass: + return visitReturnStmt(cast(S)); + case Stmt::IfStmtClass: + return visitIfStmt(cast(S)); + case Stmt::BreakStmtClass: + return visitBreakStmt(cast(S)); + case Stmt::ContinueStmtClass: + return visitContinueStmt(cast(S)); + case Stmt::SwitchStmtClass: + return visitSwitchStmt(cast(S)); + case Stmt::CaseStmtClass: + case Stmt::DefaultStmtClass: + return visitCaseStmt(cast(S)); + case Stmt::CXXForRangeStmtClass: + return visitCXXForRangeStmt(cast(S)); + case Stmt::NullStmtClass: + return true; + default: { + if (auto *Exp = dyn_cast(S)) + return this->discard(Exp); + return this->bail(S); + } + } +} + +template +bool ByteCodeStmtGen::visitCompoundStmt( + const CompoundStmt *CompoundStmt) { + BlockScope Scope(this); + for (auto *InnerStmt : CompoundStmt->body()) + if (!visitStmt(InnerStmt)) + return false; + return true; +} + +template +bool ByteCodeStmtGen::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 ByteCodeStmtGen::visitForStmt(const ForStmt *FS) { + // Compile the initialisation statement in an outer scope. + BlockScope OuterScope(this); + if (auto *Init = FS->getInit()) + if (!visitStmt(Init)) + return false; + + LabelTy LabelStart = this->getLabel(); + LabelTy LabelEnd = this->getLabel(); + + // Compile the condition, body and increment in the loop scope. + this->emitLabel(LabelStart); + { + BlockScope InnerScope(this); + + if (auto *Cond = FS->getCond()) { + if (auto *CondDecl = FS->getConditionVariableDeclStmt()) + if (!visitDeclStmt(CondDecl)) + return false; + + if (!this->visit(Cond)) + return false; + + if (!this->jumpFalse(LabelEnd)) + return false; + } + + if (auto *Body = FS->getBody()) { + LabelTy LabelSkip = this->getLabel(); + LoopScope FlowScope(this, LabelEnd, LabelSkip); + if (!visitStmt(Body)) + return false; + this->emitLabel(LabelSkip); + } + + if (auto *Inc = FS->getInc()) { + ExprScope IncScope(this); + if (!this->discard(Inc)) + return false; + } + if (!this->jump(LabelStart)) + return false; + } + this->emitLabel(LabelEnd); + return true; +} + +template +bool ByteCodeStmtGen::visitWhileStmt(const WhileStmt *WS) { + LabelTy LabelStart = this->getLabel(); + LabelTy LabelEnd = this->getLabel(); + + this->emitLabel(LabelStart); + { + BlockScope InnerScope(this); + if (auto *CondDecl = WS->getConditionVariableDeclStmt()) + if (!visitDeclStmt(CondDecl)) + return false; + + if (!this->visit(WS->getCond())) + return false; + + if (!this->jumpFalse(LabelEnd)) + return false; + + { + LoopScope FlowScope(this, LabelEnd, LabelStart); + if (!visitStmt(WS->getBody())) + return false; + } + if (!this->jump(LabelStart)) + return false; + } + this->emitLabel(LabelEnd); + + return true; +} + +template +bool ByteCodeStmtGen::visitDoStmt(const DoStmt *DS) { + LabelTy LabelStart = this->getLabel(); + LabelTy LabelEnd = this->getLabel(); + LabelTy LabelSkip = this->getLabel(); + + this->emitLabel(LabelStart); + { + { + LoopScope FlowScope(this, LabelEnd, LabelSkip); + if (!visitStmt(DS->getBody())) + return false; + this->emitLabel(LabelSkip); + } + + { + ExprScope CondScope(this); + if (!this->visitBool(DS->getCond())) + return false; + } + + if (!this->jumpTrue(LabelStart)) + return false; + } + this->emitLabel(LabelEnd); + + return true; +} + +template +bool ByteCodeStmtGen::visitReturnStmt(const ReturnStmt *RS) { + if (const Expr *RE = RS->getRetValue()) { + ExprScope RetScope(this); + if (ReturnType) { + // Primitive types are simply returned. + if (!this->visit(RE)) + return false; + this->emitCleanup(); + return this->emitRet(*ReturnType, RS); + } else { + // RVO - construct the value in the return location. + auto ReturnLocation = [this, RE] { return this->emitGetParamPtr(0, RE); }; + if (!this->visitInitializer(RE, ReturnLocation)) + return false; + this->emitCleanup(); + return this->emitRetVoid(RS); + } + } else { + this->emitCleanup(); + if (!this->emitRetVoid(RS)) + return false; + return true; + } +} + +template +bool ByteCodeStmtGen::visitIfStmt(const IfStmt *IS) { + BlockScope IfScope(this); + if (auto *CondInit = IS->getInit()) + if (!visitStmt(IS->getInit())) + return false; + + if (const DeclStmt *CondDecl = IS->getConditionVariableDeclStmt()) + if (!visitDeclStmt(CondDecl)) + return false; + + if (!this->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 (!visitStmt(IS->getThen())) + return false; + if (!this->jump(LabelEnd)) + return false; + this->emitLabel(LabelElse); + if (!visitStmt(Else)) + return false; + this->emitLabel(LabelEnd); + } else { + LabelTy LabelEnd = this->getLabel(); + if (!this->jumpFalse(LabelEnd)) + return false; + if (!visitStmt(IS->getThen())) + return false; + this->emitLabel(LabelEnd); + } + + return true; +} + +template +bool ByteCodeStmtGen::visitBreakStmt(const BreakStmt *BS) { + if (!BreakLabel) + return this->bail(BS); + return this->jump(*BreakLabel); +} + +template +bool ByteCodeStmtGen::visitContinueStmt(const ContinueStmt *CS) { + if (!ContinueLabel) + return this->bail(CS); + return this->jump(*ContinueLabel); +} + +template +bool ByteCodeStmtGen::visitSwitchStmt(const SwitchStmt *SS) { + BlockScope InnerScope(this); + + if (Optional T = this->classify(SS->getCond()->getType())) { + // The condition is stored in a local and fetched for every test. + unsigned Off = this->allocateLocalPrimitive(SS->getCond(), *T, + /*isConst=*/true); + + // Compile the condition in its own scope. + { + ExprScope CondScope(this); + if (const Stmt *CondInit = SS->getInit()) + if (!visitStmt(SS->getInit())) + return false; + + if (const DeclStmt *CondDecl = SS->getConditionVariableDeclStmt()) + if (!visitDeclStmt(CondDecl)) + return false; + + if (!this->visit(SS->getCond())) + return false; + + if (!this->emitSetLocal(*T, Off, SS->getCond())) + return false; + } + + LabelTy LabelEnd = this->getLabel(); + + // Generate code to inspect all case labels, jumping to the matched one. + const DefaultStmt *Default = nullptr; + CaseMap Labels; + for (auto *SC = SS->getSwitchCaseList(); SC; SC = SC->getNextSwitchCase()) { + LabelTy Label = this->getLabel(); + Labels.insert({SC, Label}); + + if (auto *DS = dyn_cast(SC)) { + Default = DS; + continue; + } + + if (auto *CS = dyn_cast(SC)) { + if (!this->emitGetLocal(*T, Off, CS)) + return false; + if (!this->visit(CS->getLHS())) + return false; + + if (auto *RHS = CS->getRHS()) { + if (!this->visit(CS->getRHS())) + return false; + if (!this->emitInRange(*T, CS)) + return false; + } else { + if (!this->emitEQ(*T, CS)) + return false; + } + + if (!this->jumpTrue(Label)) + return false; + continue; + } + + return this->bail(SS); + } + + // If a case wasn't matched, jump to default or skip the body. + if (!this->jump(Default ? Labels[Default] : LabelEnd)) + return false; + OptLabelTy DefaultLabel = Default ? Labels[Default] : OptLabelTy{}; + + // Compile the body, using labels defined previously. + SwitchScope LabelScope(this, std::move(Labels), LabelEnd, + DefaultLabel); + if (!visitStmt(SS->getBody())) + return false; + this->emitLabel(LabelEnd); + return true; + } else { + return this->bail(SS); + } +} + +template +bool ByteCodeStmtGen::visitCaseStmt(const SwitchCase *CS) { + auto It = CaseLabels.find(CS); + if (It == CaseLabels.end()) + return this->bail(CS); + + this->emitLabel(It->second); + return visitStmt(CS->getSubStmt()); +} + +template +bool ByteCodeStmtGen::visitCXXForRangeStmt(const CXXForRangeStmt *FS) { + BlockScope Scope(this); + + // Emit the optional init-statement. + if (auto *Init = FS->getInit()) { + if (!visitStmt(Init)) + return false; + } + + // Initialise the __range variable. + if (!visitStmt(FS->getRangeStmt())) + return false; + + // Create the __begin and __end iterators. + if (!visitStmt(FS->getBeginStmt()) || !visitStmt(FS->getEndStmt())) + return false; + + LabelTy LabelStart = this->getLabel(); + LabelTy LabelEnd = this->getLabel(); + + this->emitLabel(LabelStart); + { + // Lower the condition. + if (!this->visitBool(FS->getCond())) + return false; + if (!this->jumpFalse(LabelEnd)) + return false; + + // Lower the loop var and body, marking labels for continue/break. + { + BlockScope InnerScope(this); + if (!visitStmt(FS->getLoopVarStmt())) + return false; + + LabelTy LabelSkip = this->getLabel(); + { + LoopScope FlowScope(this, LabelEnd, LabelSkip); + + if (!visitStmt(FS->getBody())) + return false; + } + this->emitLabel(LabelSkip); + } + + // Increment: ++__begin + if (!visitStmt(FS->getInc())) + return false; + if (!this->jump(LabelStart)) + return false; + } + this->emitLabel(LabelEnd); + return true; +} + +template +bool ByteCodeStmtGen::visitVarDecl(const VarDecl *VD) { + auto DT = VD->getType(); + + if (!VD->hasLocalStorage()) { + // No code generation required. + return true; + } + + // Integers, pointers, primitives. + if (Optional T = this->classify(DT)) { + auto Off = this->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. + if (auto Off = this->allocateLocal(VD)) { + return this->visitLocalInitializer(VD->getInit(), *Off); + } else { + return this->bail(VD); + } + } +} + +template +bool ByteCodeStmtGen::visitCtorInit(Record *This, + const CXXCtorInitializer *Ctor) { + auto *Init = Ctor->getInit(); + if (auto *Base = Ctor->getBaseClass()) { + auto *Decl = Base->getAs()->getDecl(); + return this->visitBaseInitializer(Init, [this, &This, Init, Ctor, Decl] { + if (Ctor->isBaseVirtual()) + return this->emitGetPtrThisVirtBase(Decl, Init); + else + return this->emitGetPtrThisBase(This->getBase(Decl)->Offset, Init); + }); + } + + if (const FieldDecl *FD = Ctor->getMember()) { + ExprScope Scope(this); + return this->withField(FD, [this, FD, Init, This](const Record::Field *F) { + if (Optional T = this->classify(FD->getType())) { + // Primitive type, can be computed and set. + if (!this->visit(Init)) + return false; + if (This->isUnion()) + return this->emitInitThisFieldActive(*T, F->Offset, Init); + if (F->Decl->isBitField()) + return this->emitInitThisBitField(*T, F, Init); + return this->emitInitThisField(*T, F->Offset, Init); + } else { + // Nested structures. + return this->visitInitializer(Init, [this, F, Init] { + return this->emitGetPtrThisField(F->Offset, Init); + }); + } + }); + } + + if (auto *FD = Ctor->getIndirectMember()) { + auto *Init = Ctor->getInit(); + if (Optional T = this->classify(Init->getType())) { + ArrayRef Chain = FD->chain(); + Record *R = This; + for (unsigned I = 0, N = Chain.size(); I < N; ++I) { + const bool IsUnion = R->isUnion(); + auto *Member = cast(Chain[I]); + auto MemberTy = Member->getType(); + + auto *FD = R->getField(Member); + if (!FD) + return this->bail(Member); + + const unsigned Off = FD->Offset; + if (I + 1 == N) { + // Last member - set the field. + if (!this->visit(Init)) + return false; + if (IsUnion) { + return this->emitInitFieldActive(*T, Off, Init); + } else { + return this->emitInitFieldPop(*T, Off, Init); + } + } else { + // Next field must be a record - fetch it. + R = this->getRecord(cast(MemberTy)->getDecl()); + if (!R) + return this->bail(Member); + + if (IsUnion) { + if (I == 0) { + // Base member - activate this pointer. + if (!this->emitGetPtrActiveThisField(Off, Member)) + return false; + } else { + // Intermediate - active subfield. + if (!this->emitGetPtrActiveField(Off, Member)) + return false; + } + } else { + if (I == 0) { + // Base member - get this pointer. + if (!this->emitGetPtrThisField(Off, Member)) + return false; + } else { + // Intermediate - get pointer. + if (!this->emitGetPtrField(Off, Member)) + return false; + } + } + } + } + } else { + return this->bail(FD); + } + + return true; + } + + llvm_unreachable("unknown base initializer kind"); +} + +namespace clang { +namespace interp { + +template class ByteCodeStmtGen; + +} // namespace interp +} // namespace clang 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,36 @@ +set(LLVM_LINK_COMPONENTS + ) + +clang_tablegen(Opcodes.inc + -gen-clang-opcodes + SOURCE Opcodes.td + TARGET Opcodes) + +add_clang_library(clangInterp + Block.cpp + Builtin.cpp + ByteCodeEmitter.cpp + ByteCodeExprGen.cpp + ByteCodeGenError.cpp + ByteCodeStmtGen.cpp + Context.cpp + Descriptor.cpp + Disasm.cpp + EvalEmitter.cpp + Frame.cpp + Function.cpp + HeapUtils.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,100 @@ +//===--- 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; } + /// Returns CHAR_BIT. + unsigned getCharBit() const; + + /// Classifies an expression. + llvm::Optional classify(QualType T); + +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,159 @@ +//===--- 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 "ByteCodeExprGen.h" +#include "ByteCodeStmtGen.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 = ByteCodeStmtGen(*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) { + ByteCodeExprGen C(*this, *P, Parent, Stk, Result); + return Check(Parent, C.interpretExpr(E)); +} + +InterpResult Context::evaluateAsInitializer(State &Parent, const VarDecl *VD, + APValue &Result) { + ByteCodeExprGen 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() || T->isPointerType()) { + if (T->isFunctionPointerType()) + return PT_FnPtr; + 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; + default: + return PT_SintFP; + } + } + + if (T->isUnsignedIntegerOrEnumerationType()) { + switch (Ctx.getIntWidth(T)) { + case 64: + return PT_Uint64; + case 32: + return PT_Uint32; + case 16: + return PT_Uint16; + case 8: + return PT_Uint8; + default: + return PT_UintFP; + } + } + + if (T->isRealFloatingType()) + return PT_RealFP; + + if (T->isNullPtrType()) + return PT_Ptr; + + if (T->isMemberPointerType()) + return PT_MemPtr; + + if (T->isFunctionProtoType()) + return PT_FnPtr; + + if (auto *AT = dyn_cast(T)) + return classify(AT->getValueType()); + + return {}; +} + +unsigned Context::getCharBit() const { + return Ctx.getTargetInfo().getCharWidth(); +} + +InterpResult Context::Run(State &Parent, Function *Func, APValue &Result) { + InterpResult Flag; + { + InterpState State(Parent, *P, Stk, *this); + State.Current = new InterpFrame(State, Func, nullptr, {}, {}); + if (Interpret(State, Result)) { + Flag = InterpResult::Success; + } else { + Flag = InterpResult::Fail; + } + } + + if (Flag != InterpResult::Success) + Stk.clear(); + return Flag; +} + +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,222 @@ +//===--- 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 IsConst, + 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 { +private: + /// 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; + + /// Value to denote arrays of unknown size. + static constexpr unsigned UnknownSizeMark = (unsigned)-1; + +public: + /// Token to denote structures of unknown size. + struct UnknownSize {}; + + /// Pointer to the record, if block contains records. + Record *const ElemRecord = nullptr; + /// Descriptor of the array element. + Descriptor *const ElemDesc = nullptr; + /// Type of primitive elements. + llvm::Optional ElemTy = {}; + /// Flag indicating if the block is mutable. + const bool IsConst = false; + /// Flag indicating if a field 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; + + /// Allocates a descriptor for a primitive. + Descriptor(const DeclTy &D, PrimType Type, bool IsConst, bool IsTemporary, + bool IsMutable); + + /// Allocates a descriptor for an array of primitives. + Descriptor(const DeclTy &D, PrimType Type, size_t NumElems, bool IsConst, + bool IsTemporary, bool IsMutable); + + /// Allocates a descriptor for an array of primitives of unknown size. + Descriptor(const DeclTy &D, PrimType Type, bool IsTemporary, UnknownSize); + + /// Allocates a descriptor for an array of composites. + Descriptor(const DeclTy &D, Descriptor *Elem, unsigned NumElems, bool IsConst, + bool IsTemporary, bool IsMutable); + + /// Allocates a descriptor for an array of composites of unknown size. + Descriptor(const DeclTy &D, Descriptor *Elem, bool IsTemporary, UnknownSize); + + /// Allocates a descriptor for a record. + Descriptor(const DeclTy &D, Record *R, bool IsConst, bool IsTemporary, + bool IsMutable); + + QualType getType() const; + SourceLocation getLocation() const; + + const Decl *asDecl() const { return Source.dyn_cast(); } + const Expr *asExpr() const { return Source.dyn_cast(); } + + const ValueDecl *asValueDecl() const { + return dyn_cast_or_null(asDecl()); + } + + const FieldDecl *asFieldDecl() const { + return dyn_cast_or_null(asDecl()); + } + + const RecordDecl *asRecordDecl() const { + return dyn_cast_or_null(asDecl()); + } + + /// Returns the size of the object without metadata. + unsigned getSize() const { + assert(!isUnknownSizeArray() && "Array of unknown size"); + return Size; + } + + /// Returns the allocated size, including metadata. + unsigned getAllocSize() const { return AllocSize; } + /// returns the size of an element when the structure is viewed as an array. + unsigned getElemSize() const { return ElemSize; } + + /// Returns the number of elements stored in the block. + unsigned getNumElems() const { + return Size == UnknownSizeMark ? 0 : (getSize() / getElemSize()); + } + + /// Checks if the descriptor is of an array of primitives. + bool isPrimitiveArray() const { return IsArray && !ElemDesc; } + /// Checks if the descriptor is of an array of zero size. + bool isZeroSizeArray() const { return Size == 0; } + /// Checks if the descriptor is of an array of unknown size. + bool isUnknownSizeArray() const { return Size == UnknownSizeMark; } + + /// Checks if the descriptor is of a primitive. + bool isPrimitive() const { return !IsArray && !ElemRecord; } + + /// Checks if the descriptor is of an array. + bool isArray() const { return IsArray; } +}; + +/// 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 storage is constant or not. + /// Relevant for primitive fields. + unsigned IsConst : 1; + /// For primitive fields, it indicates if the field was initialized. + /// Primitive fields in static storage are always initialized. + /// Arrays are always initialized, even though their elements might not be. + /// Base classes are initialized after the constructor is invoked. + 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; + /// Flag indicating if the field is mutable (if in a record). + unsigned IsMutable : 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,292 @@ +//===--- 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, 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, 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 IsConst, bool IsMutable, + bool IsActive, Descriptor *D) { + const unsigned NumElems = D->getNumElems(); + const unsigned ElemSize = + D->ElemDesc->getAllocSize() + 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->IsInitialized = true; + Desc->IsBase = false; + Desc->IsActive = IsActive; + Desc->IsConst = IsConst || D->IsConst; + Desc->IsMutable = IsMutable || D->IsMutable; + if (auto Fn = D->ElemDesc->CtorFn) + Fn(B, ElemLoc, Desc->IsConst, Desc->IsMutable, IsActive, D->ElemDesc); + } +} + +static void dtorArrayDesc(Block *B, char *Ptr, Descriptor *D) { + const unsigned NumElems = D->getNumElems(); + const unsigned ElemSize = + D->ElemDesc->getAllocSize() + 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->getAllocSize() + 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 IsConst, bool IsMutable, + bool IsActive, Descriptor *D) { + const bool IsUnion = D->ElemRecord->isUnion(); + auto CtorSub = [=](unsigned SubOff, Descriptor *F, bool IsBase) { + auto *Desc = reinterpret_cast(Ptr + SubOff) - 1; + Desc->Offset = SubOff; + Desc->Desc = F; + Desc->IsInitialized = (B->isStatic() || F->IsArray) && !IsBase; + Desc->IsBase = IsBase; + Desc->IsActive = IsActive && !IsUnion; + Desc->IsConst = IsConst || F->IsConst; + Desc->IsMutable = IsMutable || F->IsMutable; + if (auto Fn = F->CtorFn) + Fn(B, Ptr + SubOff, Desc->IsConst, Desc->IsMutable, Desc->IsActive, F); + }; + 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 *F) { + if (auto Fn = F->DtorFn) + Fn(B, Ptr + SubOff, F); + }; + 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) { + COMPOSITE_TYPE_SWITCH(Type, return ctorTy, return nullptr); +} + +static BlockDtorFn getDtorPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return dtorTy, return nullptr); +} + +static BlockMoveFn getMovePrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return moveTy, return nullptr); +} + +static BlockCtorFn getCtorArrayPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return ctorArrayTy, return nullptr); +} + +static BlockDtorFn getDtorArrayPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return dtorArrayTy, return nullptr); +} + +static BlockMoveFn getMoveArrayPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return moveArrayTy, return nullptr); +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsConst, + bool IsTemporary, bool IsMutable) + : Source(D), ElemSize(primSize(Type)), Size(ElemSize), AllocSize(Size), + ElemTy(Type), IsConst(IsConst), IsMutable(IsMutable), + IsTemporary(IsTemporary), CtorFn(getCtorPrim(Type)), + DtorFn(getDtorPrim(Type)), MoveFn(getMovePrim(Type)) { + assert(Source && "Missing source"); +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, size_t NumElems, + bool IsConst, bool IsTemporary, bool IsMutable) + : Source(D), ElemSize(primSize(Type)), Size(ElemSize * NumElems), + AllocSize(align(Size) + sizeof(InitMap *)), ElemTy(Type), + IsConst(IsConst), IsMutable(IsMutable), IsTemporary(IsTemporary), + IsArray(true), CtorFn(getCtorArrayPrim(Type)), + DtorFn(getDtorArrayPrim(Type)), MoveFn(getMoveArrayPrim(Type)) { + assert(Source && "Missing source"); +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsTemporary, + UnknownSize) + : Source(D), ElemSize(primSize(Type)), Size(UnknownSizeMark), + AllocSize(alignof(void *)), ElemTy(Type), IsConst(true), IsMutable(false), + IsTemporary(IsTemporary), IsArray(true), CtorFn(getCtorArrayPrim(Type)), + DtorFn(getDtorArrayPrim(Type)), MoveFn(getMoveArrayPrim(Type)) { + assert(Source && "Missing source"); +} + +Descriptor::Descriptor(const DeclTy &D, Descriptor *Elem, unsigned NumElems, + bool IsConst, bool IsTemporary, bool IsMutable) + : Source(D), ElemSize(Elem->getAllocSize() + sizeof(InlineDescriptor)), + Size(ElemSize * NumElems), + AllocSize(std::max(alignof(void *), Size)), ElemDesc(Elem), + IsConst(IsConst), IsMutable(IsMutable), IsTemporary(IsTemporary), + IsArray(true), CtorFn(ctorArrayDesc), DtorFn(dtorArrayDesc), + MoveFn(moveArrayDesc) { + assert(Source && "Missing source"); +} + +Descriptor::Descriptor(const DeclTy &D, Descriptor *Elem, bool IsTemporary, + UnknownSize) + : Source(D), ElemSize(Elem->getAllocSize() + sizeof(InlineDescriptor)), + Size(UnknownSizeMark), AllocSize(alignof(void *)), ElemDesc(Elem), + IsConst(true), IsMutable(false), IsTemporary(IsTemporary), IsArray(true), + CtorFn(ctorArrayDesc), DtorFn(dtorArrayDesc), MoveFn(moveArrayDesc) { + assert(Source && "Missing source"); +} + +Descriptor::Descriptor(const DeclTy &D, Record *R, bool IsConst, + bool IsTemporary, bool IsMutable) + : Source(D), ElemSize(std::max(alignof(void *), R->getFullSize())), + Size(ElemSize), AllocSize(Size), ElemRecord(R), IsConst(IsConst), + IsMutable(IsMutable), IsTemporary(IsTemporary), CtorFn(ctorRecord), + DtorFn(dtorRecord), MoveFn(moveRecord) { + assert(Source && "Missing source"); +} + +QualType Descriptor::getType() const { + if (auto *E = asExpr()) + return E->getType(); + if (auto *D = asValueDecl()) + return D->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)) { + const std::string &Name = Cons->getParent()->getNameAsString(); + OS << Name << "::" << Name << ":\n"; + } else { + OS << F->getNameAsString() << ":\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,129 @@ +//===--- 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 visitExpr(const Expr *E) = 0; + virtual bool visitDecl(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; } + + /// Helper to invoke a method. + bool ExecuteCall(Function *F, Pointer &&This, const SourceInfo &Info); + /// Helper to emit a diagnostic on a missing method. + bool ExecuteNoCall(const FunctionDecl *F, const SourceInfo &Info); + +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,308 @@ +//===--- 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 "HeapUtils.h" +#include "Interp.h" +#include "Opcode.h" +#include "Program.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +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->visitExpr(E)) + return true; + if (BailLocation) + return llvm::make_error(*BailLocation); + return false; +} + +llvm::Expected EvalEmitter::interpretDecl(const VarDecl *VD) { + if (this->visitDecl(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 = std::make_unique(sizeof(Block) + D->getAllocSize()); + 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; +} + +bool EvalEmitter::emitInvoke(Function *Fn, const SourceInfo &Info) { + if (!isActive()) + return true; + + Pointer This = S.Stk.pop(); + if (!S.CheckInvoke(OpPC, This)) + return false; + if (S.checkingPotentialConstantExpression()) + return false; + + // Interpret the method in its own frame. + return ExecuteCall(Fn, std::move(This), Info); +} + +bool EvalEmitter::emitCall(Function *Fn, const SourceInfo &Info) { + if (!isActive()) + return true; + if (S.checkingPotentialConstantExpression()) + return false; + + // Interpret the function in its own frame. + return ExecuteCall(Fn, Pointer(), Info); +} + +bool EvalEmitter::emitVirtualInvoke(const CXXMethodDecl *MD, + const SourceInfo &Info) { + // Get the this pointer, ensure it's live. + Pointer This = S.Stk.pop(); + if (!S.CheckInvoke(OpPC, This)) + return false; + if (S.checkingPotentialConstantExpression()) + return false; + + // Dispatch to the virtual method. + CurrentSource = Info; + const CXXMethodDecl *Override = VirtualLookup(This, MD); + if (!S.CheckPure(OpPC, Override)) + return false; + if (Expected Func = P.getOrCreateFunction(Override)) { + if (*Func) { + return ExecuteCall(*Func, std::move(This), Info); + } else { + return ExecuteNoCall(Override, Info); + } + } else { + // Failed to compile method - bail out. + return false; + } +} + +template bool EvalEmitter::emitRet(const SourceInfo &Info) { + if (!isActive()) + return true; + using T = typename PrimConv::T; + return PrimitiveToValue(S.Stk.pop(), Result); +} + bool EvalEmitter::emitRetVoid(const SourceInfo &Info) { return true; } + +bool EvalEmitter::emitRetValue(const SourceInfo &Info) { + // Method to recursively traverse composites. + std::function Composite; + + + // Return the composite type. + return PointerToValue(S.Stk.pop(), Result); +} + +bool EvalEmitter::emitGetPtrLocal(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(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(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(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; +} + +bool EvalEmitter::emitNoCall(const FunctionDecl *F, const SourceInfo &Info) { + if (S.checkingPotentialConstantExpression()) + return false; + return ExecuteNoCall(F, Info); +} + +bool EvalEmitter::emitNoInvoke(const CXXMethodDecl *F, const SourceInfo &Info) { + if (S.checkingPotentialConstantExpression()) + return false; + return ExecuteNoCall(F, Info); +} + +bool EvalEmitter::emitIndirectCall(const SourceInfo &Info) { + if (S.checkingPotentialConstantExpression()) + return false; + + const FnPointer &FnPtr = S.Stk.pop(); + if (FnPtr.isZero()) { + S.FFDiag(Info); + return false; + } + + if (Function *F = FnPtr.asFunction()) + return ExecuteCall(F, Pointer(), Info); + + const FunctionDecl *Decl = FnPtr.asDecl(); + if (Expected Func = S.P.getOrCreateFunction(Decl)) { + if (*Func) + return ExecuteCall(*Func, Pointer(), Info); + else + return ExecuteNoCall(Decl, Info); + } else { + consumeError(Func.takeError()); + return false; + } +} + +bool EvalEmitter::emitIndirectInvoke(const SourceInfo &Info) { + if (S.checkingPotentialConstantExpression()) + return false; + + // Fetch and validate the object and the pointer. + const MemberPointer &Field = S.Stk.pop(); + Pointer This = S.Stk.pop(); + if (!S.CheckInvoke(OpPC, This)) + return false; + if (Field.isZero()) { + S.FFDiag(Info); + return false; + } + + // Fetch a pointer to the member function. + const CXXMethodDecl *Method = IndirectLookup(This, Field); + if (!Method) + return false; + if (!S.CheckPure(OpPC, Method)) + return false; + + // Execute the function. + if (Expected Func = S.P.getOrCreateFunction(Method)) { + if (*Func) + return ExecuteCall(*Func, std::move(This), Info); + else + return ExecuteNoCall(Method, Info); + } else { + consumeError(Func.takeError()); + return false; + } +} + +bool EvalEmitter::ExecuteCall(Function *F, Pointer &&This, + const SourceInfo &Info) { + CurrentSource = Info; + if (!S.CheckCallable(OpPC, F)) + return false; + S.Current = new InterpFrame(S, F, S.Current, OpPC, std::move(This)); + return Interpret(S, Result); +} + +bool EvalEmitter::ExecuteNoCall(const FunctionDecl *F, const SourceInfo &Info) { + S.FFDiag(Info, diag::note_constexpr_invalid_function, 1) + << F->isConstexpr() << (bool)dyn_cast(F) << F; + S.Note(F->getLocation(), diag::note_declared_at); + return false; +} + +//===----------------------------------------------------------------------===// +// 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,172 @@ +//===--- 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]; } + + /// Solves a call relocation. + void relocateCall(CodePtr Loc, Function *Callee); + + /// Solves an invoke relocation. + void relocateInvoke(CodePtr Loc, Function *Callee); + + /// 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; + + /// Checks if the function is a constructor. + bool isConstructor() const { return isa(F); } + + /// Checks if the function was default. + bool isDefaulted() const { return F->isDefaulted(); } + +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,67 @@ +//===--- 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; +} + +void Function::relocateCall(CodePtr Loc, Function *Callee) { + using namespace llvm::support; + + char *Ptr = Code.data() + (Loc - getCodeBegin()); + const auto Addr = reinterpret_cast(Callee); + *(reinterpret_cast(Ptr) - 1) = OP_Call; + + endian::write(Ptr, Addr); +} + +void Function::relocateInvoke(CodePtr Loc, Function *Callee) { + using namespace llvm::support; + + char *Ptr = Code.data() + (Loc - getCodeBegin()); + const auto Addr = reinterpret_cast(Callee); + *(reinterpret_cast(Ptr) - 1) = OP_Invoke; + + endian::write(Ptr, Addr); +} + +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; }); + assert(It != SrcMap.end() && It->first == Offset); + 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/HeapUtils.h b/clang/lib/AST/Interp/HeapUtils.h new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/HeapUtils.h @@ -0,0 +1,34 @@ +//===--- HeapUtils.h - Utilities to handle the heap -------------*- 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_HEAPUTILS_H +#define LLVM_CLANG_AST_INTERP_HEAPUTILS_H + +#include "Pointer.h" +#include "Source.h" + +namespace clang { +namespace interp { + +/// Convers a primitive value to an APValue. +template bool PrimitiveToValue(const T &V, APValue &R) { + R = V.toAPValue(); + return true; +} + +/// Converts a composite value to an APValue. +bool PointerToValue(const Pointer &Ptr, APValue &Result); + +/// Copies a union. +bool CopyUnion(InterpState &S, CodePtr OpPC, const Pointer &From, + const Pointer &To); + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/HeapUtils.cpp b/clang/lib/AST/Interp/HeapUtils.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/AST/Interp/HeapUtils.cpp @@ -0,0 +1,262 @@ +//===--- HeapUtils.cpp - Utilities to handle the heap -----------*- 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 "HeapUtils.h" +#include "InterpState.h" +#include "Record.h" +#include "Type.h" +#include "clang/AST/Type.h" +#include "llvm/ADT/APFloat.h" +#include "llvm/ADT/APSInt.h" + +using namespace clang; +using namespace interp; + +//===----------------------------------------------------------------------===// +// Pointer to APValue conversion +//===----------------------------------------------------------------------===// + +static llvm::APSInt GetInt(PrimType Ty, const Pointer &Ptr) { + INT_TYPE_SWITCH(Ty, return Ptr.deref().toAPSInt()); +} + +static llvm::APFloat GetFloat(const Pointer &Ptr) { + return Ptr.deref().toAPFloat(); +} + +static bool PointerToValue(QualType Ty, const Pointer &Ptr, APValue &Result); + +static bool RecordToValue(const Pointer &Ptr, APValue &Result) { + auto *Record = Ptr.getRecord(); + assert(Record && "Missing record descriptor"); + + bool Ok = true; + if (Record->isUnion()) { + const FieldDecl *ActiveField = nullptr; + APValue Value; + for (auto &F : Record->fields()) { + const Pointer &FP = Ptr.atField(F.Offset); + if (FP.isActive()) { + if (llvm::Optional T = F.Desc->ElemTy) { + TYPE_SWITCH(*T, Ok &= PrimitiveToValue(FP.deref(), Value)); + } else { + Ok &= PointerToValue(F.Desc->getType(), FP, Value); + } + break; + } + } + Result = APValue(ActiveField, Value); + } else { + unsigned NF = Record->getNumFields(); + unsigned NB = Record->getNumBases(); + unsigned NV = Ptr.isBaseClass() ? 0 : Record->getNumVirtualBases(); + + Result = APValue(APValue::UninitStruct(), NB, NF); + + for (unsigned I = 0; I < NF; ++I) { + const Record::Field *FD = Record->getField(I); + const Pointer &FP = Ptr.atField(FD->Offset); + APValue &Value = Result.getStructField(I); + + if (llvm::Optional T = FD->Desc->ElemTy) { + TYPE_SWITCH(*T, Ok &= PrimitiveToValue(FP.deref(), Value)); + } else { + Ok &= PointerToValue(FD->Decl->getType(), FP, Value); + } + } + + for (unsigned I = 0; I < NB; ++I) { + const Record::Base *BD = Record->getBase(I); + const Pointer &BP = Ptr.atField(BD->Offset); + Ok &= RecordToValue(BP, Result.getStructBase(I)); + } + + for (unsigned I = 0; I < NV; ++I) { + const Record::Base *VD = Record->getVirtualBase(I); + const Pointer &VP = Ptr.atField(VD->Offset); + Ok &= RecordToValue(VP, Result.getStructBase(NB + I)); + } + } + return Ok; +} + +static bool ArrayToValue(QualType ElemTy, const Pointer &Ptr, APValue &Result) { + const size_t NumElems = Ptr.getNumElems(); + Result = APValue(APValue::UninitArray{}, NumElems, NumElems); + + bool Ok = true; + for (unsigned I = 0; I < NumElems; ++I) { + APValue &Slot = Result.getArrayInitializedElt(I); + const Pointer &EP = Ptr.atIndex(I); + if (llvm::Optional T = Ptr.elementPrimType()) { + TYPE_SWITCH(*T, Ok &= PrimitiveToValue(EP.deref(), Slot)); + } else { + Ok &= PointerToValue(ElemTy, EP.narrow(), Slot); + } + } + return Ok; +} + +static bool ComplexToValue(const Pointer &Ptr, APValue &Result) { + const Pointer &PtrReal = Ptr.atIndex(0); + const Pointer &PtrImag = Ptr.atIndex(1); + switch (PrimType T = *Ptr.elementPrimType()) { + case PT_Sint8: + case PT_Uint8: + case PT_Sint16: + case PT_Uint16: + case PT_Sint32: + case PT_Uint32: + case PT_Sint64: + case PT_Uint64: + case PT_SintFP: + case PT_UintFP: + Result = APValue(GetInt(T, PtrReal), GetInt(T, PtrImag)); + return true; + + case PT_RealFP: + Result = APValue(GetFloat(PtrReal), GetFloat(PtrImag)); + return true; + + default: + llvm_unreachable("invalid complex element"); + } +} + +static bool PointerToValue(QualType Ty, const Pointer &Ptr, APValue &Result) { + if (auto *AT = Ty->getAs()) + Ty = AT->getValueType(); + + if (auto *RT = Ty->getAs()) + return RecordToValue(Ptr, Result); + + if (auto *AT = Ty->getAsArrayTypeUnsafe()) { + return ArrayToValue(AT->getElementType(), Ptr, Result); + } + + if (auto *CT = Ty->getAs()) + return ComplexToValue(Ptr, Result); + + llvm_unreachable("invalid pointer to convert"); +} + +//===----------------------------------------------------------------------===// +// Pointer deep copy +//===----------------------------------------------------------------------===// + +static bool Copy(InterpState &S, CodePtr OpPC, const Pointer &From, + const Pointer &To); + +static bool CopyRecord(InterpState &S, CodePtr OpPC, const Pointer &From, + const Pointer &To) { + auto *R = From.getRecord(); + for (auto &Field : R->fields()) { + unsigned Offset = Field.Offset; + const auto &ToField = To.atField(Offset); + const auto &FromField = From.atField(Offset); + if (!Copy(S, OpPC, FromField, ToField)) + return false; + } + + for (auto &Base : R->bases()) { + unsigned Offset = Base.Offset; + const auto &ToField = To.atField(Offset); + const auto &FromField = From.atField(Offset); + if (!CopyRecord(S, OpPC, FromField, ToField)) + return false; + ToField.initialize(); + } + + if (!From.isBaseClass()) { + for (auto &Virt : R->virtual_bases()) { + unsigned Offset = Virt.Offset; + const auto &ToField = To.atField(Offset); + const auto &FromField = From.atField(Offset); + if (!CopyRecord(S, OpPC, FromField, ToField)) + return false; + ToField.initialize(); + } + } + + return true; +} + +static bool CopyArray(InterpState &S, CodePtr OpPC, const Pointer &From, + const Pointer &To) { + if (llvm::Optional T = From.elementPrimType()) { + for (unsigned I = 0; I < From.getNumElems(); ++I) { + const auto &FromField = From.atIndex(I).narrow(); + const auto &ToField = To.atIndex(I).narrow(); + TYPE_SWITCH(*T, ToField.deref() = FromField.deref()) + ToField.initialize(); + ToField.activate(); + } + } else { + for (unsigned I = 0; I < From.getNumElems(); ++I) { + const auto &FromField = From.atIndex(I).narrow(); + if (!S.CheckLoad(OpPC, FromField)) + return false; + const auto &ToField = To.atIndex(I).narrow(); + if (!Copy(S, OpPC, FromField, ToField)) + return false; + ToField.initialize(); + ToField.activate(); + } + } + return true; +} + +static bool Copy(InterpState &S, CodePtr OpPC, const Pointer &From, + const Pointer &To) { + if (From.inArray()) + return CopyArray(S, OpPC, From, To); + + if (Record *R = From.getRecord()) { + if (R->isUnion()) + return CopyUnion(S, OpPC, From, To); + else + return CopyRecord(S, OpPC, From, To); + } + + if (llvm::Optional T = From.elementPrimType()) { + if (!S.CheckLoad(OpPC, From)) + return false; + TYPE_SWITCH(*T, To.deref() = From.deref()); + To.initialize(); + To.activate(); + return true; + } + + llvm_unreachable("invalid pointer to copy"); +} + +namespace clang { +namespace interp { + +bool PointerToValue(const Pointer &Ptr, APValue &Result) { + return ::PointerToValue(Ptr.getType(), Ptr, Result); +} + +bool CopyUnion(InterpState &S, CodePtr OpPC, const Pointer &From, + const Pointer &To) { + for (auto &Field : From.getRecord()->fields()) { + unsigned Offset = Field.Offset; + const auto &FromField = From.atField(Offset); + const auto &ToField = To.atField(Offset); + if (!FromField.isActive()) + continue; + if (!Copy(S, OpPC, FromField, ToField)) + return false; + ToField.activate(); + return true; + } + return true; +} + +} // namespace interp +} // namespace clang 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,477 @@ +//===--- 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 "clang/AST/APValue.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 { + if (Signed) + return APSInt(toAPSInt().sextOrTrunc(NumBits), !Signed); + else + return APSInt(toAPSInt().zextOrTrunc(NumBits), !Signed); + } + APValue toAPValue() const { return APValue(toAPSInt()); } + + 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()); + } + + Integral truncate(unsigned TruncBits) const { + if (TruncBits >= Bits) + return *this; + const T BitMask = (T(1) << T(TruncBits)) - 1; + const T SignBit = T(1) << (TruncBits - 1); + const T ExtMask = ~BitMask; + return Integral((V & BitMask) | (Signed && (V & SignBit) ? ExtMask : 0)); + } + + 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(toAPSInt().sextOrTrunc(NumBits), !Signed); + else + return APSInt(toAPSInt().zextOrTrunc(NumBits), !Signed); + } + APValue toAPValue() const { return APValue(toAPSInt()); } + + 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(); } + + constexpr static bool isSigned() { 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(); } + + Integral truncate(unsigned TruncBits) const { + if (TruncBits >= bitWidth()) + return *this; + return Integral(V.trunc(TruncBits).extend(bitWidth())); + } + + 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; +} + +template <> +inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, + Integral<1, false> B) { + OS << (B.isZero() ? "false" : "true"); + 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,1591 @@ +//===--- 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 "HeapUtils.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; + +template inline bool IsTrue(const T &V) { return !V.isZero(); } + +/// Finds the record to which a pointer points and ajudsts this to it. +Record *PointerLookup(Pointer &This, const MemberPointer &Field); + +/// Finds a virtual override and adjusts This to point to the object. +const CXXMethodDecl *VirtualLookup(Pointer &This, const CXXMethodDecl *MD); + +/// Indirect method lookup. +const CXXMethodDecl *IndirectLookup(Pointer &This, const MemberPointer &Ptr); + +//===----------------------------------------------------------------------===// +// 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.getSource(OpPC).asExpr(); + 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); +} + +template +bool RealArithHelper(InterpState &S, CodePtr OpPC) { + const Real &RHS = S.Stk.pop(); + const Real &LHS = S.Stk.pop(); + + Real Result = Op(LHS, RHS, M); + S.Stk.push(Result); + if (!Result.isNaN()) + return true; + + const SourceInfo &Src = S.getSource(OpPC); + S.CCEDiag(Src, diag::note_constexpr_float_arithmetic) << Result.isNaN(); + return S.noteUndefinedBehavior(); +} + +template <> inline bool Add(InterpState &S, CodePtr OpPC) { + return RealArithHelper(S, OpPC); +} + +template <> inline bool Sub(InterpState &S, CodePtr OpPC) { + return RealArithHelper(S, OpPC); +} + +template <> inline bool Mul(InterpState &S, CodePtr OpPC) { + return RealArithHelper(S, OpPC); +} + +//===----------------------------------------------------------------------===// +// 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.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.getSource(OpPC).asExpr(), 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 <> inline bool Div(InterpState &S, CodePtr OpPC) { + const Real RHS = S.Stk.pop(); + const Real LHS = S.Stk.pop(); + + if (RHS.isZero()) { + S.FFDiag(S.getSource(OpPC), diag::note_expr_divide_by_zero); + return false; + } + S.Stk.push(Real::div(LHS, RHS, APFloat::rmNearestTiesToEven)); + return true; +} + +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.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 (LHS.isZero() || RHS.isZero()) { + if (LHS.isZero() && RHS.isZero()) + S.Stk.push(BoolT::from(Fn(ComparisonCategoryResult::Equal))); + else + S.Stk.push(BoolT::from(Fn(ComparisonCategoryResult::Nonequal))); + return true; + } + + 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 auto &RHS = S.Stk.pop(); + const auto &LHS = S.Stk.pop(); + + auto CheckVirtual = [OpPC, &S](const MemberPointer &Ptr) { + if (auto *MD = dyn_cast(Ptr.getDecl())) { + if (MD->isVirtual()) { + const SourceInfo &E = S.getSource(OpPC); + S.CCEDiag(E, diag::note_constexpr_compare_virtual_mem_ptr) << MD; + return false; + } + } + return true; + }; + + using CCR = ComparisonCategoryResult; + if (!LHS.getDecl() || !RHS.getDecl()) { + CCR Result = !LHS.getDecl() && !RHS.getDecl() ? CCR::Equal : CCR::Nonequal; + S.Stk.push(BoolT::from(Fn(Result))); + return true; + } + + if (!CheckVirtual(LHS) || !CheckVirtual(RHS)) + return false; + + S.Stk.push(BoolT::from(Fn(LHS == RHS ? CCR::Equal : CCR::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.getSource(OpPC).asExpr(), Value); + } + + S.Stk.push(std::negate()(Arg)); + return true; +} + +template <> +inline bool Minus(InterpState &S, CodePtr OpPC) { + S.Stk.push(Real::negate(S.Stk.pop())); + 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; +} + +template ::T> +bool ConstFP(InterpState &S, CodePtr OpPC, uint32_t Bits, uint64_t Value) { + S.Stk.push(T::from(Value, Bits)); + return true; +} + +inline bool ConstRealFP(InterpState &S, CodePtr OpPC, + const FloatingLiteral *Value) { + S.Stk.push(Real::from(Value->getValue(), Value->getSemantics())); + return true; +} + +//===----------------------------------------------------------------------===// +// ConstFn, ConstNoFn, ConstMem +//===----------------------------------------------------------------------===// + +inline bool ConstFn(InterpState &S, CodePtr OpPC, Function *Fn) { + S.Stk.push(Fn); + return true; +} + +inline bool ConstNoFn(InterpState &S, CodePtr OpPC, const FunctionDecl *FD) { + // TODO: try to compile and rewrite opcode. + S.Stk.push(FD); + return true; +} + +inline bool ConstMem(InterpState &S, CodePtr OpPC, const ValueDecl *VD) { + S.Stk.push(VD); + 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 (!S.CheckNull(OpPC, Obj, CSK_Field)) + return false; + if (!S.CheckRange(OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!S.CheckLoad(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 (!S.CheckNull(OpPC, Obj, CSK_Field)) + return false; + if (!S.CheckRange(OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!S.CheckStore(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 (!S.CheckNull(OpPC, Obj, CSK_Field)) + return false; + if (!S.CheckRange(OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!S.CheckLoad(OpPC, Field)) + return false; + S.Stk.push(Field.deref()); + return true; +} + +template ::T> +bool GetThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + if (!S.CheckLoad(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 &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + if (!S.CheckStore(OpPC, Field)) + return false; + Field.deref() = Value; + return true; +} + +template ::T> +bool GetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + auto *B = S.P.getGlobal(I); + if (isIntegral(Name) && !B->isConst()) { + const SourceInfo &E = S.getSource(OpPC); + const ValueDecl *VD = B->getDescriptor()->asValueDecl(); + S.FFDiag(E, diag::note_constexpr_ltor_non_const_int, 1) << VD; + S.Note(VD->getLocation(), diag::note_declared_at); + return false; + } + if (B->isExtern()) + return false; + S.Stk.push(B->deref()); + return true; +} + +template ::T> +bool SetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + // TODO: emit warning. + return false; +} + +template ::T> +bool InitGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.P.getGlobal(I)->deref() = S.Stk.pop(); + return true; +} + +template ::T> +bool InitThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + Field.deref() = S.Stk.pop(); + Field.initialize(); + return true; +} + +template ::T> +bool InitThisBitField(InterpState &S, CodePtr OpPC, const Record::Field *F) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + const Pointer &Field = This.atField(F->Offset); + const auto &Value = S.Stk.pop(); + Field.deref() = Value.truncate(F->Decl->getBitWidthValue(S.getCtx())); + Field.initialize(); + return true; +} + +template ::T> +bool InitThisFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + const Pointer &Field = This.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.peek().atField(I); + Field.deref() = Value; + Field.activate(); + Field.initialize(); + return true; +} + +template ::T> +bool InitFieldPop(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 InitFieldPeek(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop(); + const Pointer &Field = S.Stk.peek().atField(I); + Field.deref() = Value; + Field.activate(); + Field.initialize(); + S.Stk.push(Value); + return true; +} + +template ::T> +bool InitBitField(InterpState &S, CodePtr OpPC, const Record::Field *F) { + const T &Value = S.Stk.pop(); + const Pointer &Field = S.Stk.pop().atField(F->Offset); + Field.deref() = Value.truncate(F->Decl->getBitWidthValue(S.getCtx())); + 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 (!S.CheckNull(OpPC, Ptr, CSK_Field)) + return false; + if (!S.CheckRange(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 &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + S.Stk.push(This.atField(Off)); + return true; +} + +inline bool GetPtrActiveField(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop(); + if (!S.CheckNull(OpPC, Ptr, CSK_Field)) + return false; + if (!S.CheckRange(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 (!S.CheckThis(OpPC, This)) + 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 (!S.CheckNull(OpPC, Ptr, CSK_Base)) + return false; + S.Stk.push(Ptr.atField(Off)); + return true; +} + +inline bool GetPtrThisBase(InterpState &S, CodePtr OpPC, uint32_t Off) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + S.Stk.push(This.atField(Off)); + return true; +} + +inline bool VirtBaseHelper(InterpState &S, CodePtr OpPC, const RecordDecl *Decl, + const Pointer &Ptr) { + Pointer Base = Ptr; + while (Base.isBaseClass()) + Base = Base.getBase(); + + auto *Field = Base.getRecord()->getVirtualBase(Decl); + S.Stk.push(Base.atField(Field->Offset)); + return true; +} + +inline bool GetPtrVirtBase(InterpState &S, CodePtr OpPC, const RecordDecl *D) { + const Pointer &Ptr = S.Stk.pop(); + if (!S.CheckNull(OpPC, Ptr, CSK_Base)) + return false; + return VirtBaseHelper(S, OpPC, D, Ptr); +} + +inline bool GetPtrThisVirtBase(InterpState &S, CodePtr OpPC, + const RecordDecl *D) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!S.CheckThis(OpPC, This)) + return false; + return VirtBaseHelper(S, OpPC, D, S.Current->getThis()); +} + +inline bool GetPtrFieldIndirect(InterpState &S, CodePtr OpPC) { + // Fetch a pointer to the member. + const MemberPointer &Field = S.Stk.pop(); + + // Fetch and validate the object. + Pointer Ptr = S.Stk.pop(); + if (!S.CheckNull(OpPC, Ptr, CSK_Field)) + return false; + if (!S.CheckRange(OpPC, Ptr, CSK_Field)) + return false; + + // Validate the pointer. + if (Field.isZero()) { + S.FFDiag(S.getSource(OpPC)); + return false; + } + + // Find the correct class in the hierarchy and fetch the pointer. + if (auto *Decl = dyn_cast(Field.getDecl())) { + if (Record *R = PointerLookup(Ptr, Field)) { + S.Stk.push(Ptr.atField(R->getField(Decl)->Offset)); + return true; + } + } + + S.FFDiag(S.getSource(OpPC)); + return false; +} + +//===----------------------------------------------------------------------===// +// Load, Store, Init +//===----------------------------------------------------------------------===// + +template ::T> +bool Load(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.peek(); + if (!S.CheckLoad(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 (!S.CheckLoad(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 (!S.CheckStore(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 (!S.CheckStore(OpPC, Ptr)) + return false; + Ptr.deref() = Value; + return true; +} + +template ::T> +bool StoreBitField(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.peek(); + if (!S.CheckStore(OpPC, Ptr)) + return false; + if (auto *FD = Ptr.getField()) { + Ptr.deref() = Value.truncate(FD->getBitWidthValue(S.getCtx())); + } else { + Ptr.deref() = Value; + } + return true; +} + +template ::T> +bool StoreBitFieldPop(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.pop(); + if (!S.CheckStore(OpPC, Ptr)) + return false; + if (auto *FD = Ptr.getField()) { + Ptr.deref() = Value.truncate(FD->getBitWidthValue(S.getCtx())); + } else { + 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 (!S.CheckInit(OpPC, Ptr)) + return false; + Ptr.initialize(); + new (&Ptr.deref()) T(Value); + return true; +} + +template ::T> +bool InitElem(InterpState &S, CodePtr OpPC, uint32_t Idx) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.peek().atIndex(Idx); + if (!S.CheckInit(OpPC, Ptr)) + return false; + Ptr.initialize(); + new (&Ptr.deref()) T(Value); + return true; +} + +template ::T> +bool InitElemPop(InterpState &S, CodePtr OpPC, uint32_t Idx) { + const T &Value = S.Stk.pop(); + const Pointer &Ptr = S.Stk.pop().atIndex(Idx); + if (!S.CheckInit(OpPC, Ptr)) + return false; + Ptr.initialize(); + new (&Ptr.deref()) T(Value); + return true; +} + +inline bool Initialise(InterpState &S, CodePtr OpPC) { + S.Stk.pop().initialize(); + return true; +} + +inline bool Activate(InterpState &S, CodePtr OpPC) { + S.Stk.pop().activate(); + 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 (!S.CheckNull(OpPC, Ptr, CSK_ArrayIndex)) + return false; + if (!S.CheckRange(OpPC, Ptr, CSK_ArrayToPointer)) + return false; + + // Get a version of the index comparable to the type. + T Index = T::from(Ptr.getIndex(), Offset.bitWidth()); + // A zero offset does not change the pointer, but in the case of an array + // it has to be adjusted to point to the first element instead of the array. + if (Offset.isZero()) { + S.Stk.push(Index.isZero() ? Ptr.atIndex(0) : Ptr); + return true; + } + // Arrays of unknown bounds cannot have pointers into them. + if (!S.CheckArray(OpPC, Ptr)) + return false; + + // Compute the largest index into the array. + unsigned MaxIndex = Ptr.getNumElems(); + + // Helper to report an invalid offset, computed as APSInt. + auto InvalidOffset = [&]() { + const unsigned Bits = Offset.bitWidth(); + APSInt APOffset(Offset.toAPSInt().extend(Bits + 2), false); + APSInt APIndex(Index.toAPSInt().extend(Bits + 2), false); + APSInt NewIndex = Add ? (APIndex + APOffset) : (APIndex - APOffset); + S.CCEDiag(S.getSource(OpPC), diag::note_constexpr_array_index) + << NewIndex + << /*array*/ static_cast(!Ptr.inArray()) + << 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); + S.Stk.push(Ptr.atIndex(static_cast(Result))); + 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, const fltSemantics *Sema) { + using T = typename PrimConv::T; + S.Stk.push(Real::from(S.Stk.pop(), *Sema)); + return true; +} + +template +bool RealToIntHelper(InterpState &S, CodePtr OpPC, const APFloat &Value, + uintptr_t Bits) { + APSInt Result(Bits, !U::isSigned()); + bool Ignored; + + // Conver to int and check for overflow. + if (Value.convertToInteger(Result, llvm::APFloat::rmTowardZero, &Ignored) & + APFloat::opInvalidOp) { + const Expr *E = S.getSource(OpPC).asExpr(); + S.CCEDiag(E, diag::note_constexpr_overflow) << Value << E->getType(); + return S.noteUndefinedBehavior(); + } + + S.Stk.push(Result); + return true; +} + +template +bool CastRealFPToAlu(InterpState &S, CodePtr OpPC) { + using T = typename PrimConv::T; + using U = typename PrimConv::T; + return RealToIntHelper(S, OpPC, S.Stk.pop().toAPFloat(), U::bitWidth()); +} + +template +bool CastRealFPToAluFP(InterpState &S, CodePtr OpPC, uint32_t Bits) { + using T = typename PrimConv::T; + using U = typename PrimConv::T; + return RealToIntHelper(S, OpPC, S.Stk.pop().toAPFloat(), Bits); +} + +//===----------------------------------------------------------------------===// +// CastMemberToBase, CastMemberToDerived +//===----------------------------------------------------------------------===// + +inline bool CastMemberToBase(InterpState &S, CodePtr OpPC, + const CXXRecordDecl *R) { + if (S.Stk.peek().toBase(R)) + return true; + S.FFDiag(S.getSource(OpPC)); + return false; +} + +inline bool CastMemberToDerived(InterpState &S, CodePtr OpPC, + const CXXRecordDecl *R) { + if (S.Stk.peek().toDerived(R)) + return true; + S.FFDiag(S.getSource(OpPC)); + return false; +} + +//===----------------------------------------------------------------------===// +// PointerBitCast, DynCastWarning +//===----------------------------------------------------------------------===// + +inline bool PointerBitCast(InterpState &S, CodePtr OpPC) { + auto *E = S.getSource(OpPC).asExpr(); + if (E->getType()->isVoidPointerType()) + S.CCEDiag(E, diag::note_constexpr_invalid_cast) << 3 << E->getType(); + else + S.CCEDiag(E, diag::note_constexpr_invalid_cast) << 2; + + // TODO: invalidate pointer. + return false; +} + +inline bool ReinterpretCastWarning(InterpState &S, CodePtr OpPC) { + auto *E = S.getSource(OpPC).asExpr(); + S.CCEDiag(E, diag::note_constexpr_invalid_cast) << 0; + return true; +} + +inline bool DynamicCastWarning(InterpState &S, CodePtr OpPC) { + auto *E = S.getSource(OpPC).asExpr(); + S.CCEDiag(E, diag::note_constexpr_invalid_cast) << 1; + return true; +} + +//===----------------------------------------------------------------------===// +// CastToDerived +//===----------------------------------------------------------------------===// + +inline bool CastToDerived(InterpState &S, CodePtr OpPC, const Expr *E) { + QualType Ty = E->getType(); + if (const PointerType *PT = Ty->getAs()) + Ty = PT->getPointeeType(); + + Pointer Base = S.Stk.pop(); + if (!S.CheckNull(OpPC, Base, CSK_Derived)) + return false; + + if (auto *R = S.P.getOrCreateRecord(Ty->getAs()->getDecl())) { + // Traverse the chain of bases (actually derived classes). + while (Base.isBaseClass()) { + // Step to deriving class. + Base = Base.getBase(); + + // Found the derived class. + if (Base.getRecord() == R) { + S.Stk.push(std::move(Base)); + return true; + } + } + } + + // Emit the diagnostic. + S.CCEDiag(E, diag::note_constexpr_invalid_downcast) << Base.getType() << Ty; + return false; +} + +//===----------------------------------------------------------------------===// +// 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.getSource(OpPC)); + return false; + } + + // Get the pointer to the object to mutate. + const Pointer &Ptr = S.Stk.pop(); + if (!S.CheckLoad(OpPC, Ptr, AK) || !S.CheckStore(OpPC, Ptr, AK)) + return false; + + // Return the original value. + const T Arg = Ptr.deref(); + S.Stk.push(Arg); + + // Perform the operation. + return Op(S, OpPC, Arg, Ptr.deref()); +} + +template +bool Pre(InterpState &S, CodePtr OpPC, AccessKinds AK, IncDecFn Op) { + // Bail if not C++14. + if (!S.getLangOpts().CPlusPlus14 && !S.keepEvaluatingAfterFailure()) { + S.FFDiag(S.getSource(OpPC)); + return false; + } + + // Read the value to mutate. + Pointer Ptr = S.Stk.peek(); + if (!S.CheckLoad(OpPC, Ptr, AK) || !S.CheckStore(OpPC, Ptr, AK)) + return false; + + // Perform the operation. + const T Arg = Ptr.deref(); + return Op(S, OpPC, Arg, Ptr.deref()); +} + +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.getSource(OpPC).asExpr(), Value); + } +} + +template