diff options
Diffstat (limited to 'clang/lib/AST/Interp')
45 files changed, 8172 insertions, 0 deletions
diff --git a/clang/lib/AST/Interp/Block.cpp b/clang/lib/AST/Interp/Block.cpp new file mode 100644 index 000000000000..5fc93eb39f4e --- /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<DeadBlock *>(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/Block.h b/clang/lib/AST/Interp/Block.h new file mode 100644 index 000000000000..97fb9a3ca096 --- /dev/null +++ b/clang/lib/AST/Interp/Block.h @@ -0,0 +1,140 @@ +//===--- 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<unsigned> &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; } + /// Returns the size of the block. + InterpSize getSize() const { return Desc->getAllocSize(); } + /// Returns the declaration ID. + llvm::Optional<unsigned> getDeclID() const { return DeclID; } + + /// Returns a pointer to the stored data. + char *data() { return reinterpret_cast<char *>(this + 1); } + + /// Returns a view over the data. + template <typename T> + T &deref() { return *reinterpret_cast<T *>(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<unsigned> 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/Boolean.h b/clang/lib/AST/Interp/Boolean.h new file mode 100644 index 000000000000..3e6c8b5da9f0 --- /dev/null +++ b/clang/lib/AST/Interp/Boolean.h @@ -0,0 +1,148 @@ +//===--- Boolean.h - Wrapper for boolean 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_BOOLEAN_H +#define LLVM_CLANG_AST_INTERP_BOOLEAN_H + +#include <cstddef> +#include <cstdint> +#include "Integral.h" +#include "clang/AST/APValue.h" +#include "clang/AST/ComparisonCategories.h" +#include "llvm/ADT/APSInt.h" +#include "llvm/Support/MathExtras.h" +#include "llvm/Support/raw_ostream.h" + +namespace clang { +namespace interp { + +/// Wrapper around boolean types. +class Boolean { + private: + /// Underlying boolean. + bool V; + + /// Construct a wrapper from a boolean. + explicit Boolean(bool V) : V(V) {} + + public: + /// Zero-initializes a boolean. + Boolean() : V(false) {} + + bool operator<(Boolean RHS) const { return V < RHS.V; } + bool operator>(Boolean RHS) const { return V > RHS.V; } + bool operator<=(Boolean RHS) const { return V <= RHS.V; } + bool operator>=(Boolean RHS) const { return V >= RHS.V; } + bool operator==(Boolean RHS) const { return V == RHS.V; } + bool operator!=(Boolean RHS) const { return V != RHS.V; } + + bool operator>(unsigned RHS) const { return static_cast<unsigned>(V) > RHS; } + + Boolean operator-() const { return Boolean(V); } + Boolean operator~() const { return Boolean(true); } + + 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(1, static_cast<uint64_t>(V), false), true); + } + APSInt toAPSInt(unsigned NumBits) const { + return APSInt(toAPSInt().zextOrTrunc(NumBits), true); + } + APValue toAPValue() const { return APValue(toAPSInt()); } + + Boolean toUnsigned() const { return *this; } + + constexpr static unsigned bitWidth() { return true; } + bool isZero() const { return !V; } + bool isMin() const { return isZero(); } + + constexpr static bool isMinusOne() { return false; } + + constexpr static bool isSigned() { return false; } + + constexpr static bool isNegative() { return false; } + constexpr static bool isPositive() { return !isNegative(); } + + ComparisonCategoryResult compare(const Boolean &RHS) const { + return Compare(V, RHS.V); + } + + unsigned countLeadingZeros() const { return V ? 0 : 1; } + + Boolean truncate(unsigned TruncBits) const { return *this; } + + void print(llvm::raw_ostream &OS) const { OS << (V ? "true" : "false"); } + + static Boolean min(unsigned NumBits) { return Boolean(false); } + static Boolean max(unsigned NumBits) { return Boolean(true); } + + template <typename T> + static typename std::enable_if<std::is_integral<T>::value, Boolean>::type + from(T Value) { + return Boolean(Value != 0); + } + + template <unsigned SrcBits, bool SrcSign> + static typename std::enable_if<SrcBits != 0, Boolean>::type from( + Integral<SrcBits, SrcSign> Value) { + return Boolean(!Value.isZero()); + } + + template <bool SrcSign> + static Boolean from(Integral<0, SrcSign> Value) { + return Boolean(!Value.isZero()); + } + + static Boolean zero() { return from(false); } + + template <typename T> + static Boolean from(T Value, unsigned NumBits) { + return Boolean(Value); + } + + static bool inRange(int64_t Value, unsigned NumBits) { + return Value == 0 || Value == 1; + } + + static bool increment(Boolean A, Boolean *R) { + *R = Boolean(true); + return false; + } + + static bool decrement(Boolean A, Boolean *R) { + llvm_unreachable("Cannot decrement booleans"); + } + + static bool add(Boolean A, Boolean B, unsigned OpBits, Boolean *R) { + *R = Boolean(A.V || B.V); + return false; + } + + static bool sub(Boolean A, Boolean B, unsigned OpBits, Boolean *R) { + *R = Boolean(A.V ^ B.V); + return false; + } + + static bool mul(Boolean A, Boolean B, unsigned OpBits, Boolean *R) { + *R = Boolean(A.V && B.V); + return false; + } +}; + +inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Boolean &B) { + B.print(OS); + return OS; +} + +} // 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 index 000000000000..7a4569820a1d --- /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<Function *> 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<PrimType, 8> ParamTypes; + llvm::DenseMap<unsigned, Function::ParamDescriptor> 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<PrimType> 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<ByteCodeGenError>(*BailLocation); + else + return Func; + } else { + // Create scopes from descriptors. + llvm::SmallVector<Scope, 2> 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<int64_t>(Reloc); + endian::write<int32_t, endianness::native, 1>(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 <typename... Tys> +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<unsigned>::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<const char *>(&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<int>{ + (emit(reinterpret_cast<const char *>(&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/ByteCodeEmitter.h b/clang/lib/AST/Interp/ByteCodeEmitter.h new file mode 100644 index 000000000000..03452a350c96 --- /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 "PrimType.h" +#include "Program.h" +#include "Source.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<Function *> 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<const ParmVarDecl *, unsigned> Params; + /// Local descriptors. + llvm::SmallVector<SmallVector<Local, 8>, 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<SourceLocation> BailLocation; + /// Label information for linker. + llvm::DenseMap<LabelTy, unsigned> LabelOffsets; + /// Location of label relocations. + llvm::DenseMap<LabelTy, llvm::SmallVector<unsigned, 5>> LabelRelocs; + /// Program code. + std::vector<char> 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 <typename... Tys> + 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/ByteCodeExprGen.cpp b/clang/lib/AST/Interp/ByteCodeExprGen.cpp new file mode 100644 index 000000000000..5c8cb4274260 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeExprGen.cpp @@ -0,0 +1,580 @@ +//===--- 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 "PrimType.h" +#include "Program.h" +#include "State.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +template <typename T> using Expected = llvm::Expected<T>; +template <typename T> using Optional = llvm::Optional<T>; + +namespace clang { +namespace interp { + +/// Scope used to handle temporaries in toplevel variable declarations. +template <class Emitter> class DeclScope final : public LocalScope<Emitter> { +public: + DeclScope(ByteCodeExprGen<Emitter> *Ctx, const VarDecl *VD) + : LocalScope<Emitter>(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 Emitter> class OptionScope { +public: + using InitFnRef = typename ByteCodeExprGen<Emitter>::InitFnRef; + using ChainedInitFnRef = std::function<bool(InitFnRef)>; + + /// Root constructor, compiling or discarding primitives. + OptionScope(ByteCodeExprGen<Emitter> *Ctx, bool NewDiscardResult) + : Ctx(Ctx), OldDiscardResult(Ctx->DiscardResult), + OldInitFn(std::move(Ctx->InitFn)) { + Ctx->DiscardResult = NewDiscardResult; + Ctx->InitFn = llvm::Optional<InitFnRef>{}; + } + + /// Root constructor, setting up compilation state. + OptionScope(ByteCodeExprGen<Emitter> *Ctx, InitFnRef NewInitFn) + : Ctx(Ctx), OldDiscardResult(Ctx->DiscardResult), + OldInitFn(std::move(Ctx->InitFn)) { + Ctx->DiscardResult = true; + Ctx->InitFn = NewInitFn; + } + + /// Extends the chain of initialisation pointers. + OptionScope(ByteCodeExprGen<Emitter> *Ctx, ChainedInitFnRef NewInitFn) + : Ctx(Ctx), OldDiscardResult(Ctx->DiscardResult), + OldInitFn(std::move(Ctx->InitFn)) { + assert(OldInitFn && "missing initializer"); + Ctx->InitFn = [this, NewInitFn] { return NewInitFn(*OldInitFn); }; + } + + ~OptionScope() { + Ctx->DiscardResult = OldDiscardResult; + Ctx->InitFn = std::move(OldInitFn); + } + +private: + /// Parent context. + ByteCodeExprGen<Emitter> *Ctx; + /// Old discard flag to restore. + bool OldDiscardResult; + /// Old pointer emitter to restore. + llvm::Optional<InitFnRef> OldInitFn; +}; + +} // namespace interp +} // namespace clang + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::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_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); + + default: { + // TODO: implement other casts. + return this->bail(CE); + } + } +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::VisitIntegerLiteral(const IntegerLiteral *LE) { + if (DiscardResult) + return true; + + auto Val = LE->getValue(); + QualType LitTy = LE->getType(); + if (Optional<PrimType> T = classify(LitTy)) + return emitConst(*T, getIntWidth(LitTy), LE->getValue(), LE); + return this->bail(LE); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::VisitParenExpr(const ParenExpr *PE) { + return this->Visit(PE->getSubExpr()); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::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_Comma: + if (!discard(LHS)) + return false; + if (!this->Visit(RHS)) + return false; + return true; + default: + break; + } + + // Typecheck the args. + Optional<PrimType> LT = classify(LHS->getType()); + Optional<PrimType> RT = classify(RHS->getType()); + if (!LT || !RT) { + return this->bail(BO); + } + + if (Optional<PrimType> T = classify(BO->getType())) { + 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_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)); + default: + return this->bail(BO); + } + } + + return this->bail(BO); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::discard(const Expr *E) { + OptionScope<Emitter> Scope(this, /*discardResult=*/true); + return this->Visit(E); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::visit(const Expr *E) { + OptionScope<Emitter> Scope(this, /*discardResult=*/false); + return this->Visit(E); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::visitBool(const Expr *E) { + if (Optional<PrimType> T = classify(E->getType())) { + return visit(E); + } else { + return this->bail(E); + } +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::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_Ptr: + return this->emitNullPtr(E); + } + llvm_unreachable("unknown primitive type"); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::dereference( + const Expr *LV, DerefKind AK, llvm::function_ref<bool(PrimType)> Direct, + llvm::function_ref<bool(PrimType)> Indirect) { + if (Optional<PrimType> T = classify(LV->getType())) { + if (!LV->refersToBitField()) { + // Only primitive, non bit-field types can be dereferenced directly. + if (auto *DE = dyn_cast<DeclRefExpr>(LV)) { + if (!DE->getDecl()->getType()->isReferenceType()) { + if (auto *PD = dyn_cast<ParmVarDecl>(DE->getDecl())) + return dereferenceParam(LV, *T, PD, AK, Direct, Indirect); + if (auto *VD = dyn_cast<VarDecl>(DE->getDecl())) + return dereferenceVar(LV, *T, VD, AK, Direct, Indirect); + } + } + } + + if (!visit(LV)) + return false; + return Indirect(*T); + } + + return false; +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::dereferenceParam( + const Expr *LV, PrimType T, const ParmVarDecl *PD, DerefKind AK, + llvm::function_ref<bool(PrimType)> Direct, + llvm::function_ref<bool(PrimType)> 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 <class Emitter> +bool ByteCodeExprGen<Emitter>::dereferenceVar( + const Expr *LV, PrimType T, const VarDecl *VD, DerefKind AK, + llvm::function_ref<bool(PrimType)> Direct, + llvm::function_ref<bool(PrimType)> 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 <class Emitter> +bool ByteCodeExprGen<Emitter>::emitConst(PrimType T, unsigned NumBits, + const APInt &Value, const Expr *E) { + switch (T) { + case PT_Sint8: + return this->emitConstSint8(Value.getSExtValue(), E); + case PT_Uint8: + return this->emitConstUint8(Value.getZExtValue(), E); + case PT_Sint16: + return this->emitConstSint16(Value.getSExtValue(), E); + case PT_Uint16: + return this->emitConstUint16(Value.getZExtValue(), E); + case PT_Sint32: + return this->emitConstSint32(Value.getSExtValue(), E); + case PT_Uint32: + return this->emitConstUint32(Value.getZExtValue(), E); + case PT_Sint64: + return this->emitConstSint64(Value.getSExtValue(), E); + case PT_Uint64: + return this->emitConstUint64(Value.getZExtValue(), E); + case PT_Bool: + return this->emitConstBool(Value.getBoolValue(), E); + case PT_Ptr: + llvm_unreachable("Invalid integral type"); + break; + } + llvm_unreachable("unknown primitive type"); +} + +template <class Emitter> +unsigned ByteCodeExprGen<Emitter>::allocateLocalPrimitive(DeclTy &&Src, + PrimType Ty, + bool IsConst, + bool IsExtended) { + Descriptor *D = P.createDescriptor(Src, Ty, IsConst, Src.is<const Expr *>()); + Scope::Local Local = this->createLocal(D); + if (auto *VD = dyn_cast_or_null<ValueDecl>(Src.dyn_cast<const Decl *>())) + Locals.insert({VD, Local}); + VarScope->add(Local, IsExtended); + return Local.Offset; +} + +template <class Emitter> +llvm::Optional<unsigned> +ByteCodeExprGen<Emitter>::allocateLocal(DeclTy &&Src, bool IsExtended) { + QualType Ty; + + const ValueDecl *Key = nullptr; + bool IsTemporary = false; + if (auto *VD = dyn_cast_or_null<ValueDecl>(Src.dyn_cast<const Decl *>())) { + Key = VD; + Ty = VD->getType(); + } + if (auto *E = Src.dyn_cast<const Expr *>()) { + 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 <class Emitter> +bool ByteCodeExprGen<Emitter>::visitInitializer( + const Expr *Init, InitFnRef InitFn) { + OptionScope<Emitter> Scope(this, InitFn); + return this->Visit(Init); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::getPtrVarDecl(const VarDecl *VD, const Expr *E) { + // Generate a pointer to the local, loading refs. + if (Optional<unsigned> Idx = getGlobalIdx(VD)) { + if (VD->getType()->isReferenceType()) + return this->emitGetGlobalPtr(*Idx, E); + else + return this->emitGetPtrGlobal(*Idx, E); + } + return this->bail(VD); +} + +template <class Emitter> +llvm::Optional<unsigned> +ByteCodeExprGen<Emitter>::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 <class Emitter> +const RecordType *ByteCodeExprGen<Emitter>::getRecordTy(QualType Ty) { + if (auto *PT = dyn_cast<PointerType>(Ty)) + return PT->getPointeeType()->getAs<RecordType>(); + else + return Ty->getAs<RecordType>(); +} + +template <class Emitter> +Record *ByteCodeExprGen<Emitter>::getRecord(QualType Ty) { + if (auto *RecordTy = getRecordTy(Ty)) { + return getRecord(RecordTy->getDecl()); + } + return nullptr; +} + +template <class Emitter> +Record *ByteCodeExprGen<Emitter>::getRecord(const RecordDecl *RD) { + return P.getOrCreateRecord(RD); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::visitExpr(const Expr *Exp) { + ExprScope<Emitter> RootScope(this); + if (!visit(Exp)) + return false; + + if (Optional<PrimType> T = classify(Exp)) + return this->emitRet(*T, Exp); + else + return this->emitRetValue(Exp); +} + +template <class Emitter> +bool ByteCodeExprGen<Emitter>::visitDecl(const VarDecl *VD) { + const Expr *Init = VD->getInit(); + + if (Optional<unsigned> I = P.createGlobal(VD)) { + if (Optional<PrimType> T = classify(VD->getType())) { + { + // Primitive declarations - compute the value and set it. + DeclScope<Emitter> 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<Emitter> 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 <class Emitter> +void ByteCodeExprGen<Emitter>::emitCleanup() { + for (VariableScope<Emitter> *C = VarScope; C; C = C->getParent()) + C->emitDestruction(); +} + +namespace clang { +namespace interp { + +template class ByteCodeExprGen<ByteCodeEmitter>; +template class ByteCodeExprGen<EvalEmitter>; + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/ByteCodeExprGen.h b/clang/lib/AST/Interp/ByteCodeExprGen.h new file mode 100644 index 000000000000..1d0e34fc991f --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeExprGen.h @@ -0,0 +1,331 @@ +//===--- 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 "PrimType.h" +#include "Record.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 Emitter> class LocalScope; +template <class Emitter> class RecordScope; +template <class Emitter> class VariableScope; +template <class Emitter> class DeclScope; +template <class Emitter> class OptionScope; + +/// Compilation context for expressions. +template <class Emitter> +class ByteCodeExprGen : public ConstStmtVisitor<ByteCodeExprGen<Emitter>, 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<bool()>; + + /// Current compilation context. + Context &Ctx; + /// Program to link to. + Program &P; + +public: + /// Initializes the compiler and the backend emitter. + template <typename... Tys> + ByteCodeExprGen(Context &Ctx, Program &P, Tys &&... Args) + : Emitter(Ctx, P, Args...), Ctx(Ctx), P(P) {} + + // Expression visitors - result returned on stack. + bool VisitCastExpr(const CastExpr *E); + bool VisitIntegerLiteral(const IntegerLiteral *E); + bool VisitParenExpr(const ParenExpr *E); + bool VisitBinaryOperator(const BinaryOperator *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); + + /// Returns the size int bits of an integer. + unsigned getIntWidth(QualType Ty) { + auto &ASTContext = Ctx.getASTContext(); + return ASTContext.getIntWidth(Ty); + } + + /// Returns the value of CHAR_BIT. + unsigned getCharBit() const { + auto &ASTContext = Ctx.getASTContext(); + return ASTContext.getTargetInfo().getCharWidth(); + } + + /// Classifies a type. + llvm::Optional<PrimType> classify(const Expr *E) const { + return E->isGLValue() ? PT_Ptr : classify(E->getType()); + } + llvm::Optional<PrimType> classify(QualType Ty) const { + return Ctx.classify(Ty); + } + + /// Checks if a pointer needs adjustment. + bool needsAdjust(QualType Ty) const { + 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 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<unsigned> allocateLocal(DeclTy &&Decl, + bool IsExtended = false); + +private: + friend class VariableScope<Emitter>; + friend class LocalScope<Emitter>; + friend class RecordScope<Emitter>; + friend class DeclScope<Emitter>; + friend class OptionScope<Emitter>; + + /// Emits a zero initializer. + bool visitZeroInitializer(PrimType T, const Expr *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<bool(PrimType)> Direct, + llvm::function_ref<bool(PrimType)> Indirect); + bool dereferenceParam(const Expr *LV, PrimType T, const ParmVarDecl *PD, + DerefKind AK, + llvm::function_ref<bool(PrimType)> Direct, + llvm::function_ref<bool(PrimType)> Indirect); + bool dereferenceVar(const Expr *LV, PrimType T, const VarDecl *PD, + DerefKind AK, llvm::function_ref<bool(PrimType)> Direct, + llvm::function_ref<bool(PrimType)> Indirect); + + /// Emits an APInt constant. + bool emitConst(PrimType T, unsigned NumBits, const llvm::APInt &Value, + const Expr *E); + + /// Emits an integer constant. + template <typename T> bool emitConst(const Expr *E, T Value) { + QualType Ty = E->getType(); + unsigned NumBits = getIntWidth(Ty); + APInt WrappedValue(NumBits, Value, std::is_signed<T>::value); + return emitConst(*Ctx.classify(Ty), NumBits, WrappedValue, E); + } + + /// Returns a pointer to a variable declaration. + bool getPtrVarDecl(const VarDecl *VD, const Expr *E); + + /// Returns the index of a global. + llvm::Optional<unsigned> getGlobalIdx(const VarDecl *VD); + + /// Emits the initialized pointer. + bool emitInitFn() { + assert(InitFn && "missing initializer"); + return (*InitFn)(); + } + +protected: + /// Variable to storage mapping. + llvm::DenseMap<const ValueDecl *, Scope::Local> Locals; + + /// OpaqueValueExpr to location mapping. + llvm::DenseMap<const OpaqueValueExpr *, unsigned> OpaqueExprs; + + /// Current scope. + VariableScope<Emitter> *VarScope = nullptr; + + /// Current argument index. + llvm::Optional<uint64_t> ArrayIndex; + + /// Flag indicating if return value is to be discarded. + bool DiscardResult = false; + + /// Expression being initialized. + llvm::Optional<InitFnRef> InitFn = {}; +}; + +extern template class ByteCodeExprGen<ByteCodeEmitter>; +extern template class ByteCodeExprGen<EvalEmitter>; + +/// Scope chain managing the variable lifetimes. +template <class Emitter> 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<Emitter> *Ctx) + : Ctx(Ctx), Parent(Ctx->VarScope) { + Ctx->VarScope = this; + } + + /// ByteCodeExprGen instance. + ByteCodeExprGen<Emitter> *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 Emitter> class LocalScope : public VariableScope<Emitter> { +public: + LocalScope(ByteCodeExprGen<Emitter> *Ctx) : VariableScope<Emitter>(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<unsigned> Idx; +}; + +/// Scope for storage declared in a compound statement. +template <class Emitter> class BlockScope final : public LocalScope<Emitter> { +public: + BlockScope(ByteCodeExprGen<Emitter> *Ctx) : LocalScope<Emitter>(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 Emitter> class ExprScope final : public LocalScope<Emitter> { +public: + ExprScope(ByteCodeExprGen<Emitter> *Ctx) : LocalScope<Emitter>(Ctx) {} + + void addExtended(const Scope::Local &Local) override { + this->Parent->addLocal(Local); + } +}; + +} // 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 index 000000000000..5fd3d77c3842 --- /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/ByteCodeGenError.h b/clang/lib/AST/Interp/ByteCodeGenError.h new file mode 100644 index 000000000000..a4fa4917705d --- /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<ByteCodeGenError> { +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/ByteCodeStmtGen.cpp b/clang/lib/AST/Interp/ByteCodeStmtGen.cpp new file mode 100644 index 000000000000..c71301598bde --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeStmtGen.cpp @@ -0,0 +1,265 @@ +//===--- 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 "PrimType.h" +#include "Program.h" +#include "State.h" + +using namespace clang; +using namespace clang::interp; + +template <typename T> using Expected = llvm::Expected<T>; +template <typename T> using Optional = llvm::Optional<T>; + +namespace clang { +namespace interp { + +/// Scope managing label targets. +template <class Emitter> class LabelScope { +public: + virtual ~LabelScope() { } + +protected: + LabelScope(ByteCodeStmtGen<Emitter> *Ctx) : Ctx(Ctx) {} + /// ByteCodeStmtGen instance. + ByteCodeStmtGen<Emitter> *Ctx; +}; + +/// Sets the context for break/continue statements. +template <class Emitter> class LoopScope final : public LabelScope<Emitter> { +public: + using LabelTy = typename ByteCodeStmtGen<Emitter>::LabelTy; + using OptLabelTy = typename ByteCodeStmtGen<Emitter>::OptLabelTy; + + LoopScope(ByteCodeStmtGen<Emitter> *Ctx, LabelTy BreakLabel, + LabelTy ContinueLabel) + : LabelScope<Emitter>(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 Emitter> class SwitchScope final : public LabelScope<Emitter> { +public: + using LabelTy = typename ByteCodeStmtGen<Emitter>::LabelTy; + using OptLabelTy = typename ByteCodeStmtGen<Emitter>::OptLabelTy; + using CaseMap = typename ByteCodeStmtGen<Emitter>::CaseMap; + + SwitchScope(ByteCodeStmtGen<Emitter> *Ctx, CaseMap &&CaseLabels, + LabelTy BreakLabel, OptLabelTy DefaultLabel) + : LabelScope<Emitter>(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 <class Emitter> +bool ByteCodeStmtGen<Emitter>::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<CXXMethodDecl>(F)) + return this->bail(MD); + + 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 <class Emitter> +bool ByteCodeStmtGen<Emitter>::visitStmt(const Stmt *S) { + switch (S->getStmtClass()) { + case Stmt::CompoundStmtClass: + return visitCompoundStmt(cast<CompoundStmt>(S)); + case Stmt::DeclStmtClass: + return visitDeclStmt(cast<DeclStmt>(S)); + case Stmt::ReturnStmtClass: + return visitReturnStmt(cast<ReturnStmt>(S)); + case Stmt::IfStmtClass: + return visitIfStmt(cast<IfStmt>(S)); + case Stmt::NullStmtClass: + return true; + default: { + if (auto *Exp = dyn_cast<Expr>(S)) + return this->discard(Exp); + return this->bail(S); + } + } +} + +template <class Emitter> +bool ByteCodeStmtGen<Emitter>::visitCompoundStmt( + const CompoundStmt *CompoundStmt) { + BlockScope<Emitter> Scope(this); + for (auto *InnerStmt : CompoundStmt->body()) + if (!visitStmt(InnerStmt)) + return false; + return true; +} + +template <class Emitter> +bool ByteCodeStmtGen<Emitter>::visitDeclStmt(const DeclStmt *DS) { + for (auto *D : DS->decls()) { + // Variable declarator. + if (auto *VD = dyn_cast<VarDecl>(D)) { + if (!visitVarDecl(VD)) + return false; + continue; + } + + // Decomposition declarator. + if (auto *DD = dyn_cast<DecompositionDecl>(D)) { + return this->bail(DD); + } + } + + return true; +} + +template <class Emitter> +bool ByteCodeStmtGen<Emitter>::visitReturnStmt(const ReturnStmt *RS) { + if (const Expr *RE = RS->getRetValue()) { + ExprScope<Emitter> 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 <class Emitter> +bool ByteCodeStmtGen<Emitter>::visitIfStmt(const IfStmt *IS) { + BlockScope<Emitter> 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 <class Emitter> +bool ByteCodeStmtGen<Emitter>::visitVarDecl(const VarDecl *VD) { + auto DT = VD->getType(); + + if (!VD->hasLocalStorage()) { + // No code generation required. + return true; + } + + // Integers, pointers, primitives. + if (Optional<PrimType> T = this->classify(DT)) { + auto Off = this->allocateLocalPrimitive(VD, *T, DT.isConstQualified()); + // Compile the initialiser in its own scope. + { + ExprScope<Emitter> 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); + } + } +} + +namespace clang { +namespace interp { + +template class ByteCodeStmtGen<ByteCodeEmitter>; + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/ByteCodeStmtGen.h b/clang/lib/AST/Interp/ByteCodeStmtGen.h new file mode 100644 index 000000000000..d9c0b64ed4b8 --- /dev/null +++ b/clang/lib/AST/Interp/ByteCodeStmtGen.h @@ -0,0 +1,89 @@ +//===--- 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 "ByteCodeEmitter.h" +#include "ByteCodeExprGen.h" +#include "EvalEmitter.h" +#include "Pointer.h" +#include "PrimType.h" +#include "Record.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 Emitter> class LoopScope; +template <class Emitter> class SwitchScope; +template <class Emitter> class LabelScope; + +/// Compilation context for statements. +template <class Emitter> +class ByteCodeStmtGen : public ByteCodeExprGen<Emitter> { + using LabelTy = typename Emitter::LabelTy; + using AddrTy = typename Emitter::AddrTy; + using OptLabelTy = llvm::Optional<LabelTy>; + using CaseMap = llvm::DenseMap<const SwitchCase *, LabelTy>; + +public: + template<typename... Tys> + ByteCodeStmtGen(Tys&&... Args) + : ByteCodeExprGen<Emitter>(std::forward<Tys>(Args)...) {} + +protected: + bool visitFunc(const FunctionDecl *F) override; + +private: + friend class LabelScope<Emitter>; + friend class LoopScope<Emitter>; + friend class SwitchScope<Emitter>; + + // Statement visitors. + bool visitStmt(const Stmt *S); + bool visitCompoundStmt(const CompoundStmt *S); + bool visitDeclStmt(const DeclStmt *DS); + bool visitReturnStmt(const ReturnStmt *RS); + bool visitIfStmt(const IfStmt *IS); + + /// Compiles a variable declaration. + bool visitVarDecl(const VarDecl *VD); + +private: + /// Type of the expression returned by the function. + llvm::Optional<PrimType> ReturnType; + + /// 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<EvalEmitter>; + +} // 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 index 000000000000..4f8f7b96e7c3 --- /dev/null +++ b/clang/lib/AST/Interp/Context.cpp @@ -0,0 +1,148 @@ +//===--- 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 "ByteCodeEmitter.h" +#include "ByteCodeExprGen.h" +#include "ByteCodeStmtGen.h" +#include "EvalEmitter.h" +#include "Interp.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "PrimType.h" +#include "Program.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<ByteCodeEmitter>(*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<EvalEmitter> C(*this, *P, Parent, Stk, Result); + return Check(Parent, C.interpretExpr(E)); +} + +InterpResult Context::evaluateAsInitializer(State &Parent, const VarDecl *VD, + APValue &Result) { + ByteCodeExprGen<EvalEmitter> C(*this, *P, Parent, Stk, Result); + return Check(Parent, C.interpretDecl(VD)); +} + +const LangOptions &Context::getLangOpts() const { return Ctx.getLangOpts(); } + +llvm::Optional<PrimType> Context::classify(QualType T) { + if (T->isReferenceType() || T->isPointerType()) { + 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 {}; + } + } + + if (T->isUnsignedIntegerOrEnumerationType()) { + switch (Ctx.getIntWidth(T)) { + case 64: + return PT_Uint64; + case 32: + return PT_Uint32; + case 16: + return PT_Uint16; + case 8: + return PT_Uint8; + default: + return {}; + } + } + + if (T->isNullPtrType()) + return PT_Ptr; + + if (auto *AT = dyn_cast<AtomicType>(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<bool> &&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/Context.h b/clang/lib/AST/Interp/Context.h new file mode 100644 index 000000000000..96368b6e5f02 --- /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<PrimType> 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<bool> &&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<Program> P; +}; + +} // 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 index 000000000000..5c1a8a9cf306 --- /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 "PrimType.h" +#include "Record.h" + +using namespace clang; +using namespace clang::interp; + +template <typename T> +static void ctorTy(Block *, char *Ptr, bool, bool, bool, Descriptor *) { + new (Ptr) T(); +} + +template <typename T> static void dtorTy(Block *, char *Ptr, Descriptor *) { + reinterpret_cast<T *>(Ptr)->~T(); +} + +template <typename T> +static void moveTy(Block *, char *Src, char *Dst, Descriptor *) { + auto *SrcPtr = reinterpret_cast<T *>(Src); + auto *DstPtr = reinterpret_cast<T *>(Dst); + new (DstPtr) T(std::move(*SrcPtr)); +} + +template <typename T> +static void ctorArrayTy(Block *, char *Ptr, bool, bool, bool, Descriptor *D) { + for (unsigned I = 0, NE = D->getNumElems(); I < NE; ++I) { + new (&reinterpret_cast<T *>(Ptr)[I]) T(); + } +} + +template <typename T> +static void dtorArrayTy(Block *, char *Ptr, Descriptor *D) { + for (unsigned I = 0, NE = D->getNumElems(); I < NE; ++I) { + reinterpret_cast<T *>(Ptr)[I].~T(); + } +} + +template <typename T> +static void moveArrayTy(Block *, char *Src, char *Dst, Descriptor *D) { + for (unsigned I = 0, NE = D->getNumElems(); I < NE; ++I) { + auto *SrcPtr = &reinterpret_cast<T *>(Src)[I]; + auto *DstPtr = &reinterpret_cast<T *>(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<InlineDescriptor *>(ElemPtr); + auto *ElemLoc = reinterpret_cast<char *>(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<InlineDescriptor *>(ElemPtr); + auto *ElemLoc = reinterpret_cast<char *>(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<InlineDescriptor *>(SrcPtr); + auto *SrcElemLoc = reinterpret_cast<char *>(SrcDesc + 1); + auto *DstDesc = reinterpret_cast<InlineDescriptor *>(DstPtr); + auto *DstElemLoc = reinterpret_cast<char *>(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<InlineDescriptor *>(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<Descriptor **>(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<T>, return nullptr); +} + +static BlockDtorFn getDtorPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return dtorTy<T>, return nullptr); +} + +static BlockMoveFn getMovePrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return moveTy<T>, return nullptr); +} + +static BlockCtorFn getCtorArrayPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return ctorArrayTy<T>, return nullptr); +} + +static BlockDtorFn getDtorArrayPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return dtorArrayTy<T>, return nullptr); +} + +static BlockMoveFn getMoveArrayPrim(PrimType Type) { + COMPOSITE_TYPE_SWITCH(Type, return moveArrayTy<T>, return nullptr); +} + +Descriptor::Descriptor(const DeclTy &D, PrimType Type, bool IsConst, + bool IsTemporary, bool IsMutable) + : Source(D), ElemSize(primSize(Type)), Size(ElemSize), AllocSize(Size), + 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 *)), 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 *)), 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<size_t>(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<size_t>(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<const Decl *>()) + return D->getLocation(); + if (auto *E = Source.dyn_cast<const Expr *>()) + 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<char *>(this) + align(sizeof(InitMap)); + return reinterpret_cast<T *>(Start); +} + +bool InitMap::initialize(unsigned I) { + unsigned Bucket = I / PER_FIELD; + unsigned Mask = 1ull << static_cast<uint64_t>(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<uint64_t>(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/Descriptor.h b/clang/lib/AST/Interp/Descriptor.h new file mode 100644 index 000000000000..b260b7600974 --- /dev/null +++ b/clang/lib/AST/Interp/Descriptor.h @@ -0,0 +1,220 @@ +//===--- 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<const Decl *, const Expr *>; + +/// 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; + /// 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 Decl *>(); } + const Expr *asExpr() const { return Source.dyn_cast<const Expr *>(); } + + const ValueDecl *asValueDecl() const { + return dyn_cast_or_null<ValueDecl>(asDecl()); + } + + const FieldDecl *asFieldDecl() const { + return dyn_cast_or_null<FieldDecl>(asDecl()); + } + + const RecordDecl *asRecordDecl() const { + return dyn_cast_or_null<RecordDecl>(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/Disasm.cpp b/clang/lib/AST/Interp/Disasm.cpp new file mode 100644 index 000000000000..e77a825eb1f2 --- /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 "PrimType.h" +#include "Program.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<CXXConstructorDecl>(F)) { + const std::string &Name = Cons->getParent()->getNameAsString(); + OS << Name << "::" << Name << ":\n"; + } else { + OS << F->getNameAsString() << ":\n"; + } + } else { + OS << "<<expr>>\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<Opcode>(); + 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.cpp b/clang/lib/AST/Interp/EvalEmitter.cpp new file mode 100644 index 000000000000..22e8695b9211 --- /dev/null +++ b/clang/lib/AST/Interp/EvalEmitter.cpp @@ -0,0 +1,253 @@ +//===--- EvalEmitter.cpp - Instruction emitter for the VM -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "EvalEmitter.h" +#include "Context.h" +#include "Interp.h" +#include "Opcode.h" +#include "Program.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; +template <typename T> using Expected = llvm::Expected<T>; + +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<bool> EvalEmitter::interpretExpr(const Expr *E) { + if (this->visitExpr(E)) + return true; + if (BailLocation) + return llvm::make_error<ByteCodeGenError>(*BailLocation); + return false; +} + +llvm::Expected<bool> EvalEmitter::interpretDecl(const VarDecl *VD) { + if (this->visitDecl(VD)) + return true; + if (BailLocation) + return llvm::make_error<ByteCodeGenError>(*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<char[]>(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<bool>()) + ActiveLabel = Label; + } + return true; +} + +bool EvalEmitter::jumpFalse(const LabelTy &Label) { + if (isActive()) { + if (!S.Stk.pop<bool>()) + ActiveLabel = Label; + } + return true; +} + +bool EvalEmitter::jump(const LabelTy &Label) { + if (isActive()) + CurrentLabel = ActiveLabel = Label; + return true; +} + +bool EvalEmitter::fallthrough(const LabelTy &Label) { + if (isActive()) + ActiveLabel = Label; + CurrentLabel = Label; + return true; +} + +template <PrimType OpType> bool EvalEmitter::emitRet(const SourceInfo &Info) { + if (!isActive()) + return true; + using T = typename PrimConv<OpType>::T; + return ReturnValue<T>(S.Stk.pop<T>(), Result); +} + +bool EvalEmitter::emitRetVoid(const SourceInfo &Info) { return true; } + +bool EvalEmitter::emitRetValue(const SourceInfo &Info) { + // Method to recursively traverse composites. + std::function<bool(QualType, const Pointer &, APValue &)> Composite; + Composite = [this, &Composite](QualType Ty, const Pointer &Ptr, APValue &R) { + if (auto *AT = Ty->getAs<AtomicType>()) + Ty = AT->getValueType(); + + if (auto *RT = Ty->getAs<RecordType>()) { + auto *Record = Ptr.getRecord(); + assert(Record && "Missing record descriptor"); + + bool Ok = true; + if (RT->getDecl()->isUnion()) { + const FieldDecl *ActiveField = nullptr; + APValue Value; + for (auto &F : Record->fields()) { + const Pointer &FP = Ptr.atField(F.Offset); + QualType FieldTy = F.Decl->getType(); + if (FP.isActive()) { + if (llvm::Optional<PrimType> T = Ctx.classify(FieldTy)) { + TYPE_SWITCH(*T, Ok &= ReturnValue<T>(FP.deref<T>(), Value)); + } else { + Ok &= Composite(FieldTy, FP, Value); + } + break; + } + } + R = APValue(ActiveField, Value); + } else { + unsigned NF = Record->getNumFields(); + unsigned NB = Record->getNumBases(); + unsigned NV = Ptr.isBaseClass() ? 0 : Record->getNumVirtualBases(); + + R = APValue(APValue::UninitStruct(), NB, NF); + + for (unsigned I = 0; I < NF; ++I) { + const Record::Field *FD = Record->getField(I); + QualType FieldTy = FD->Decl->getType(); + const Pointer &FP = Ptr.atField(FD->Offset); + APValue &Value = R.getStructField(I); + + if (llvm::Optional<PrimType> T = Ctx.classify(FieldTy)) { + TYPE_SWITCH(*T, Ok &= ReturnValue<T>(FP.deref<T>(), Value)); + } else { + Ok &= Composite(FieldTy, FP, Value); + } + } + + for (unsigned I = 0; I < NB; ++I) { + const Record::Base *BD = Record->getBase(I); + QualType BaseTy = Ctx.getASTContext().getRecordType(BD->Decl); + const Pointer &BP = Ptr.atField(BD->Offset); + Ok &= Composite(BaseTy, BP, R.getStructBase(I)); + } + + for (unsigned I = 0; I < NV; ++I) { + const Record::Base *VD = Record->getVirtualBase(I); + QualType VirtBaseTy = Ctx.getASTContext().getRecordType(VD->Decl); + const Pointer &VP = Ptr.atField(VD->Offset); + Ok &= Composite(VirtBaseTy, VP, R.getStructBase(NB + I)); + } + } + return Ok; + } + if (auto *AT = Ty->getAsArrayTypeUnsafe()) { + const size_t NumElems = Ptr.getNumElems(); + QualType ElemTy = AT->getElementType(); + R = APValue(APValue::UninitArray{}, NumElems, NumElems); + + bool Ok = true; + for (unsigned I = 0; I < NumElems; ++I) { + APValue &Slot = R.getArrayInitializedElt(I); + const Pointer &EP = Ptr.atIndex(I); + if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) { + TYPE_SWITCH(*T, Ok &= ReturnValue<T>(EP.deref<T>(), Slot)); + } else { + Ok &= Composite(ElemTy, EP.narrow(), Slot); + } + } + return Ok; + } + llvm_unreachable("invalid value to return"); + }; + + // Return the composite type. + const auto &Ptr = S.Stk.pop<Pointer>(); + return Composite(Ptr.getType(), Ptr, 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<Pointer>(reinterpret_cast<Block *>(It->second.get())); + return true; +} + +template <PrimType OpType> +bool EvalEmitter::emitGetLocal(uint32_t I, const SourceInfo &Info) { + if (!isActive()) + return true; + + using T = typename PrimConv<OpType>::T; + + auto It = Locals.find(I); + assert(It != Locals.end() && "Missing local variable"); + auto *B = reinterpret_cast<Block *>(It->second.get()); + S.Stk.push<T>(*reinterpret_cast<T *>(B + 1)); + return true; +} + +template <PrimType OpType> +bool EvalEmitter::emitSetLocal(uint32_t I, const SourceInfo &Info) { + if (!isActive()) + return true; + + using T = typename PrimConv<OpType>::T; + + auto It = Locals.find(I); + assert(It != Locals.end() && "Missing local variable"); + auto *B = reinterpret_cast<Block *>(It->second.get()); + *reinterpret_cast<T *>(B + 1) = S.Stk.pop<T>(); + 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<Block *>(It->second.get())); + } + + return true; +} + +//===----------------------------------------------------------------------===// +// Opcode evaluators +//===----------------------------------------------------------------------===// + +#define GET_EVAL_IMPL +#include "Opcodes.inc" +#undef GET_EVAL_IMPL diff --git a/clang/lib/AST/Interp/EvalEmitter.h b/clang/lib/AST/Interp/EvalEmitter.h new file mode 100644 index 000000000000..eec2ff8ee753 --- /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 "PrimType.h" +#include "Program.h" +#include "Source.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<bool> interpretExpr(const Expr *E); + llvm::Expected<bool> 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<const ParmVarDecl *, unsigned> Params; + /// Local descriptors. + llvm::SmallVector<SmallVector<Local, 8>, 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<unsigned, std::unique_ptr<char[]>> 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<SourceLocation> 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/Frame.cpp b/clang/lib/AST/Interp/Frame.cpp new file mode 100644 index 000000000000..16134aa1db36 --- /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/Frame.h b/clang/lib/AST/Interp/Frame.h new file mode 100644 index 000000000000..b9a0ea9412f8 --- /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/Function.cpp b/clang/lib/AST/Interp/Function.cpp new file mode 100644 index 000000000000..0ed13a92aa38 --- /dev/null +++ b/clang/lib/AST/Interp/Function.cpp @@ -0,0 +1,48 @@ +//===--- Function.h - Bytecode function for the VM --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Function.h" +#include "Program.h" +#include "Opcode.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +Function::Function(Program &P, const FunctionDecl *F, unsigned ArgSize, + llvm::SmallVector<PrimType, 8> &&ParamTypes, + llvm::DenseMap<unsigned, ParamDescriptor> &&Params) + : P(P), Loc(F->getBeginLoc()), F(F), ArgSize(ArgSize), + ParamTypes(std::move(ParamTypes)), Params(std::move(Params)) {} + +CodePtr Function::getCodeBegin() const { return Code.data(); } + +CodePtr Function::getCodeEnd() const { return Code.data() + Code.size(); } + +Function::ParamDescriptor Function::getParamDescriptor(unsigned Offset) const { + auto It = Params.find(Offset); + assert(It != Params.end() && "Invalid parameter offset"); + return It->second; +} + +SourceInfo Function::getSource(CodePtr PC) const { + unsigned Offset = PC - getCodeBegin(); + using Elem = std::pair<unsigned, SourceInfo>; + auto It = std::lower_bound(SrcMap.begin(), SrcMap.end(), Elem{Offset, {}}, + [](Elem A, Elem B) { return A.first < B.first; }); + if (It == SrcMap.end() || It->first != Offset) + llvm::report_fatal_error("missing source location"); + return It->second; +} + +bool Function::isVirtual() const { + if (auto *M = dyn_cast<CXXMethodDecl>(F)) + return M->isVirtual(); + return false; +} diff --git a/clang/lib/AST/Interp/Function.h b/clang/lib/AST/Interp/Function.h new file mode 100644 index 000000000000..28531f04b6e9 --- /dev/null +++ b/clang/lib/AST/Interp/Function.h @@ -0,0 +1,163 @@ +//===--- 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<Local, 8>; + + Scope(LocalVectorTy &&Descriptors) : Descriptors(std::move(Descriptors)) {} + + llvm::iterator_range<LocalVectorTy::iterator> 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<PrimType, Descriptor *>; + + /// 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<llvm::SmallVector<Scope, 2>::iterator> scopes() { + return llvm::make_range(Scopes.begin(), Scopes.end()); + } + + /// Range over argument types. + using arg_reverse_iterator = SmallVectorImpl<PrimType>::reverse_iterator; + llvm::iterator_range<arg_reverse_iterator> args_reverse() { + return llvm::make_range(ParamTypes.rbegin(), ParamTypes.rend()); + } + + /// Returns a specific scope. + Scope &getScope(unsigned Idx) { return Scopes[Idx]; } + + /// Returns the source information at a given PC. + SourceInfo getSource(CodePtr PC) const; + + /// Checks if the function is valid to call in constexpr. + bool isConstexpr() const { return IsValid; } + + /// Checks if the function is virtual. + bool isVirtual() const; + + /// Checks if the function is a constructor. + bool isConstructor() const { return isa<CXXConstructorDecl>(F); } + +private: + /// Construct a function representing an actual function. + Function(Program &P, const FunctionDecl *F, unsigned ArgSize, + llvm::SmallVector<PrimType, 8> &&ParamTypes, + llvm::DenseMap<unsigned, ParamDescriptor> &&Params); + + /// Sets the code of a function. + void setCode(unsigned NewFrameSize, std::vector<char> &&NewCode, SourceMap &&NewSrcMap, + llvm::SmallVector<Scope, 2> &&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<char> Code; + /// Opcode-to-expression mapping. + SourceMap SrcMap; + /// List of block descriptors. + llvm::SmallVector<Scope, 2> Scopes; + /// List of argument types. + llvm::SmallVector<PrimType, 8> ParamTypes; + /// Map from byte offset to parameter descriptor. + llvm::DenseMap<unsigned, ParamDescriptor> 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/Integral.h b/clang/lib/AST/Interp/Integral.h new file mode 100644 index 000000000000..7cc788070de8 --- /dev/null +++ b/clang/lib/AST/Interp/Integral.h @@ -0,0 +1,269 @@ +//===--- 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_INTEGRAL_H +#define LLVM_CLANG_AST_INTERP_INTEGRAL_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 <cstddef> +#include <cstdint> + +namespace clang { +namespace interp { + +using APInt = llvm::APInt; +using APSInt = llvm::APSInt; + +/// Helper to compare two comparable types. +template <typename T> +ComparisonCategoryResult Compare(const T &X, const T &Y) { + if (X < Y) + return ComparisonCategoryResult::Less; + if (X > Y) + return ComparisonCategoryResult::Greater; + return ComparisonCategoryResult::Equal; +} + +// Helper structure to select the representation. +template <unsigned Bits, bool Signed> struct Repr; +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; }; + +/// 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 <unsigned Bits, bool Signed> class Integral { +private: + template <unsigned OtherBits, bool OtherSigned> friend class Integral; + + // The primitive representing the integral. + using T = typename Repr<Bits, Signed>::Type; + T V; + + /// Primitive representing limits. + static const auto Min = std::numeric_limits<T>::min(); + static const auto Max = std::numeric_limits<T>::max(); + + /// Construct an integral from anything that is convertible to storage. + template <typename T> explicit Integral(T V) : V(V) {} + +public: + /// Zero-initializes an integral. + Integral() : V(0) {} + + /// Constructs an integral from another integral. + template <unsigned SrcBits, bool SrcSign> + explicit Integral(Integral<SrcBits, SrcSign> 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<unsigned>(V) > RHS; + } + + Integral operator-() const { return Integral(-V); } + Integral operator~() const { return Integral(~V); } + + template <unsigned DstBits, bool DstSign> + explicit operator Integral<DstBits, DstSign>() const { + return Integral<DstBits, DstSign>(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, static_cast<uint64_t>(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<Bits, false> toUnsigned() const { + return Integral<Bits, false>(*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 { return llvm::countLeadingZeros<T>(V); } + + 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(Min); + } + static Integral max(unsigned NumBits) { + return Integral(Max); + } + + template <typename T> + static typename std::enable_if<std::is_integral<T>::value, Integral>::type + from(T Value) { + return Integral(Value); + } + + template <unsigned SrcBits, bool SrcSign> + static typename std::enable_if<SrcBits != 0, Integral>::type + from(Integral<SrcBits, SrcSign> Value) { + return Integral(Value.V); + } + + template <bool SrcSign> 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 <typename T> static Integral from(T Value, unsigned NumBits) { + return Integral(Value); + } + + static bool inRange(int64_t Value, unsigned NumBits) { + return CheckRange<T, Min, Max>(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 <typename T> + static typename std::enable_if<std::is_signed<T>::value, bool>::type + CheckAddUB(T A, T B, T &R) { + return llvm::AddOverflow<T>(A, B, R); + } + + template <typename T> + static typename std::enable_if<std::is_unsigned<T>::value, bool>::type + CheckAddUB(T A, T B, T &R) { + R = A + B; + return false; + } + + template <typename T> + static typename std::enable_if<std::is_signed<T>::value, bool>::type + CheckSubUB(T A, T B, T &R) { + return llvm::SubOverflow<T>(A, B, R); + } + + template <typename T> + static typename std::enable_if<std::is_unsigned<T>::value, bool>::type + CheckSubUB(T A, T B, T &R) { + R = A - B; + return false; + } + + template <typename T> + static typename std::enable_if<std::is_signed<T>::value, bool>::type + CheckMulUB(T A, T B, T &R) { + return llvm::MulOverflow<T>(A, B, R); + } + + template <typename T> + static typename std::enable_if<std::is_unsigned<T>::value, bool>::type + CheckMulUB(T A, T B, T &R) { + R = A * B; + return false; + } + + template <typename T, T Min, T Max> + static typename std::enable_if<std::is_signed<T>::value, bool>::type + CheckRange(int64_t V) { + return Min <= V && V <= Max; + } + + template <typename T, T Min, T Max> + static typename std::enable_if<std::is_unsigned<T>::value, bool>::type + CheckRange(int64_t V) { + return V >= 0 && static_cast<uint64_t>(V) <= Max; + } +}; + +template <unsigned Bits, bool Signed> +llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, Integral<Bits, Signed> I) { + I.print(OS); + return OS; +} + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Interp.cpp b/clang/lib/AST/Interp/Interp.cpp new file mode 100644 index 000000000000..1a8109cedf76 --- /dev/null +++ b/clang/lib/AST/Interp/Interp.cpp @@ -0,0 +1,417 @@ +//===--- InterpState.cpp - Interpreter for the constexpr VM -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Interp.h" +#include <limits> +#include <vector> +#include "Function.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "Opcode.h" +#include "PrimType.h" +#include "Program.h" +#include "State.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/CXXInheritance.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" +#include "llvm/ADT/APSInt.h" + +using namespace clang; +using namespace clang::interp; + +//===----------------------------------------------------------------------===// +// Ret +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +static bool Ret(InterpState &S, CodePtr &PC, APValue &Result) { + S.CallStackDepth--; + const T &Ret = S.Stk.pop<T>(); + + assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame"); + if (!S.checkingPotentialConstantExpression()) + S.Current->popArgs(); + + if (InterpFrame *Caller = S.Current->Caller) { + PC = S.Current->getRetPC(); + delete S.Current; + S.Current = Caller; + S.Stk.push<T>(Ret); + } else { + delete S.Current; + S.Current = nullptr; + if (!ReturnValue<T>(Ret, Result)) + return false; + } + return true; +} + +static bool RetVoid(InterpState &S, CodePtr &PC, APValue &Result) { + S.CallStackDepth--; + + assert(S.Current->getFrameOffset() == S.Stk.size() && "Invalid frame"); + if (!S.checkingPotentialConstantExpression()) + S.Current->popArgs(); + + if (InterpFrame *Caller = S.Current->Caller) { + PC = S.Current->getRetPC(); + delete S.Current; + S.Current = Caller; + } else { + delete S.Current; + S.Current = nullptr; + } + return true; +} + +static bool RetValue(InterpState &S, CodePtr &Pt, APValue &Result) { + llvm::report_fatal_error("Interpreter cannot return values"); +} + +//===----------------------------------------------------------------------===// +// Jmp, Jt, Jf +//===----------------------------------------------------------------------===// + +static bool Jmp(InterpState &S, CodePtr &PC, int32_t Offset) { + PC += Offset; + return true; +} + +static bool Jt(InterpState &S, CodePtr &PC, int32_t Offset) { + if (S.Stk.pop<bool>()) { + PC += Offset; + } + return true; +} + +static bool Jf(InterpState &S, CodePtr &PC, int32_t Offset) { + if (!S.Stk.pop<bool>()) { + PC += Offset; + } + return true; +} + +static bool CheckInitialized(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + if (Ptr.isInitialized()) + return true; + if (!S.checkingPotentialConstantExpression()) { + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_access_uninit) << AK << false; + } + return false; +} + +static bool CheckActive(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + if (Ptr.isActive()) + return true; + + // Get the inactive field descriptor. + const FieldDecl *InactiveField = Ptr.getField(); + + // Walk up the pointer chain to find the union which is not active. + Pointer U = Ptr.getBase(); + while (!U.isActive()) { + U = U.getBase(); + } + + // Find the active field of the union. + Record *R = U.getRecord(); + assert(R && R->isUnion() && "Not a union"); + const FieldDecl *ActiveField = nullptr; + for (unsigned I = 0, N = R->getNumFields(); I < N; ++I) { + const Pointer &Field = U.atField(R->getField(I)->Offset); + if (Field.isActive()) { + ActiveField = Field.getField(); + break; + } + } + + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_access_inactive_union_member) + << AK << InactiveField << !ActiveField << ActiveField; + return false; +} + +static bool CheckTemporary(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + if (auto ID = Ptr.getDeclID()) { + if (!Ptr.isStaticTemporary()) + return true; + + if (Ptr.getDeclDesc()->getType().isConstQualified()) + return true; + + if (S.P.getCurrentDecl() == ID) + return true; + + const SourceInfo &E = S.Current->getSource(OpPC); + S.FFDiag(E, diag::note_constexpr_access_static_temporary, 1) << AK; + S.Note(Ptr.getDeclLoc(), diag::note_constexpr_temporary_here); + return false; + } + return true; +} + +static bool CheckGlobal(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (auto ID = Ptr.getDeclID()) { + if (!Ptr.isStatic()) + return true; + + if (S.P.getCurrentDecl() == ID) + return true; + + S.FFDiag(S.Current->getLocation(OpPC), diag::note_constexpr_modify_global); + return false; + } + return true; +} + +namespace clang { +namespace interp { + +bool CheckExtern(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!Ptr.isExtern()) + return true; + + if (!S.checkingPotentialConstantExpression()) { + auto *VD = Ptr.getDeclDesc()->asValueDecl(); + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_ltor_non_constexpr, 1) << VD; + S.Note(VD->getLocation(), diag::note_declared_at); + } + return false; +} + +bool CheckArray(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!Ptr.isUnknownSizeArray()) + return true; + const SourceInfo &E = S.Current->getSource(OpPC); + S.FFDiag(E, diag::note_constexpr_unsized_array_indexed); + return false; +} + +bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + const auto &Src = S.Current->getSource(OpPC); + if (Ptr.isZero()) { + + if (Ptr.isField()) + S.FFDiag(Src, diag::note_constexpr_null_subobject) << CSK_Field; + else + S.FFDiag(Src, diag::note_constexpr_access_null) << AK; + + return false; + } + + if (!Ptr.isLive()) { + bool IsTemp = Ptr.isTemporary(); + + S.FFDiag(Src, diag::note_constexpr_lifetime_ended, 1) << AK << !IsTemp; + + if (IsTemp) + S.Note(Ptr.getDeclLoc(), diag::note_constexpr_temporary_here); + else + S.Note(Ptr.getDeclLoc(), diag::note_declared_at); + + return false; + } + + return true; +} + +bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + CheckSubobjectKind CSK) { + if (!Ptr.isZero()) + return true; + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_null_subobject) << CSK; + return false; +} + +bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK) { + if (!Ptr.isOnePastEnd()) + return true; + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_access_past_end) << AK; + return false; +} + +bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + CheckSubobjectKind CSK) { + if (!Ptr.isElementPastEnd()) + return true; + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_past_end_subobject) << CSK; + return false; +} + +bool CheckConst(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + assert(Ptr.isLive() && "Pointer is not live"); + if (!Ptr.isConst()) { + return true; + } + + const QualType Ty = Ptr.getType(); + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_constexpr_modify_const_type) << Ty; + return false; +} + +bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + assert(Ptr.isLive() && "Pointer is not live"); + if (!Ptr.isMutable()) { + return true; + } + + const SourceInfo &Loc = S.Current->getSource(OpPC); + const FieldDecl *Field = Ptr.getField(); + S.FFDiag(Loc, diag::note_constexpr_access_mutable, 1) << AK_Read << Field; + S.Note(Field->getLocation(), diag::note_declared_at); + return false; +} + +bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckExtern(S, OpPC, Ptr)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckInitialized(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckActive(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckTemporary(S, OpPC, Ptr, AK_Read)) + return false; + if (!CheckMutable(S, OpPC, Ptr)) + return false; + return true; +} + +bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_Assign)) + return false; + if (!CheckExtern(S, OpPC, Ptr)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Assign)) + return false; + if (!CheckGlobal(S, OpPC, Ptr)) + return false; + if (!CheckConst(S, OpPC, Ptr)) + return false; + return true; +} + +bool CheckInvoke(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_MemberCall)) + return false; + if (!CheckExtern(S, OpPC, Ptr)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_MemberCall)) + return false; + return true; +} + +bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr) { + if (!CheckLive(S, OpPC, Ptr, AK_Assign)) + return false; + if (!CheckRange(S, OpPC, Ptr, AK_Assign)) + return false; + return true; +} + +bool CheckCallable(InterpState &S, CodePtr OpPC, Function *F) { + const SourceLocation &Loc = S.Current->getLocation(OpPC); + + if (F->isVirtual()) { + if (!S.getLangOpts().CPlusPlus2a) { + S.CCEDiag(Loc, diag::note_constexpr_virtual_call); + return false; + } + } + + if (!F->isConstexpr()) { + if (S.getLangOpts().CPlusPlus11) { + const FunctionDecl *DiagDecl = F->getDecl(); + + // If this function is not constexpr because it is an inherited + // non-constexpr constructor, diagnose that directly. + auto *CD = dyn_cast<CXXConstructorDecl>(DiagDecl); + if (CD && CD->isInheritingConstructor()) { + auto *Inherited = CD->getInheritedConstructor().getConstructor(); + if (!Inherited->isConstexpr()) + DiagDecl = CD = Inherited; + } + + // FIXME: If DiagDecl is an implicitly-declared special member function + // or an inheriting constructor, we should be much more explicit about why + // it's not constexpr. + if (CD && CD->isInheritingConstructor()) + S.FFDiag(Loc, diag::note_constexpr_invalid_inhctor, 1) + << CD->getInheritedConstructor().getConstructor()->getParent(); + else + S.FFDiag(Loc, diag::note_constexpr_invalid_function, 1) + << DiagDecl->isConstexpr() << (bool)CD << DiagDecl; + S.Note(DiagDecl->getLocation(), diag::note_declared_at); + } else { + S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr); + } + return false; + } + + return true; +} + +bool CheckThis(InterpState &S, CodePtr OpPC, const Pointer &This) { + if (!This.isZero()) + return true; + + const SourceInfo &Loc = S.Current->getSource(OpPC); + + bool IsImplicit = false; + if (auto *E = dyn_cast_or_null<CXXThisExpr>(Loc.asExpr())) + IsImplicit = E->isImplicit(); + + if (S.getLangOpts().CPlusPlus11) + S.FFDiag(Loc, diag::note_constexpr_this) << IsImplicit; + else + S.FFDiag(Loc); + + return false; +} + +bool CheckPure(InterpState &S, CodePtr OpPC, const CXXMethodDecl *MD) { + if (!MD->isPure()) + return true; + const SourceInfo &E = S.Current->getSource(OpPC); + S.FFDiag(E, diag::note_constexpr_pure_virtual_call, 1) << MD; + S.Note(MD->getLocation(), diag::note_declared_at); + return false; +} +bool Interpret(InterpState &S, APValue &Result) { + CodePtr PC = S.Current->getPC(); + + for (;;) { + auto Op = PC.read<Opcode>(); + CodePtr OpPC = PC; + + switch (Op) { +#define GET_INTERP +#include "Opcodes.inc" +#undef GET_INTERP + } + } +} + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/Interp.h b/clang/lib/AST/Interp/Interp.h new file mode 100644 index 000000000000..8934efa13b9c --- /dev/null +++ b/clang/lib/AST/Interp/Interp.h @@ -0,0 +1,960 @@ +//===--- 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 <limits> +#include <vector> +#include "Function.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "InterpState.h" +#include "Opcode.h" +#include "PrimType.h" +#include "Program.h" +#include "State.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" + +namespace clang { +namespace interp { + +using APInt = llvm::APInt; +using APSInt = llvm::APSInt; + +/// Convers a value to an APValue. +template <typename T> bool ReturnValue(const T &V, APValue &R) { + R = V.toAPValue(); + return true; +} + +/// Checks if the variable has externally defined storage. +bool CheckExtern(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if the array is offsetable. +bool CheckArray(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a pointer is live and accesible. +bool CheckLive(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK); +/// Checks if a pointer is null. +bool CheckNull(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + CheckSubobjectKind CSK); + +/// Checks if a pointer is in range. +bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + AccessKinds AK); + +/// Checks if a field from which a pointer is going to be derived is valid. +bool CheckRange(InterpState &S, CodePtr OpPC, const Pointer &Ptr, + CheckSubobjectKind CSK); + +/// Checks if a pointer points to const storage. +bool CheckConst(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a pointer points to a mutable field. +bool CheckMutable(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a value can be loaded from a block. +bool CheckLoad(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a value can be stored in a block. +bool CheckStore(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a method can be invoked on an object. +bool CheckInvoke(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a value can be initialized. +bool CheckInit(InterpState &S, CodePtr OpPC, const Pointer &Ptr); + +/// Checks if a method can be called. +bool CheckCallable(InterpState &S, CodePtr OpPC, Function *F); + +/// Checks the 'this' pointer. +bool CheckThis(InterpState &S, CodePtr OpPC, const Pointer &This); + +/// Checks if a method is pure virtual. +bool CheckPure(InterpState &S, CodePtr OpPC, const CXXMethodDecl *MD); + +template <typename T> inline bool IsTrue(const T &V) { return !V.isZero(); } + +//===----------------------------------------------------------------------===// +// Add, Sub, Mul +//===----------------------------------------------------------------------===// + +template <typename T, bool (*OpFW)(T, T, unsigned, T *), + template <typename U> 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<T>(Result); + return true; + } + + // If for some reason evaluation continues, use the truncated results. + S.Stk.push<T>(Result); + + // Slow path - compute the result using another bit of precision. + APSInt Value = OpAP<APSInt>()(LHS.toAPSInt(Bits), RHS.toAPSInt(Bits)); + + // Report undefined behaviour, stopping if required. + const Expr *E = S.Current->getExpr(OpPC); + QualType Type = E->getType(); + if (S.checkingForUndefinedBehavior()) { + 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 <PrimType Name, class T = typename PrimConv<Name>::T> +bool Add(InterpState &S, CodePtr OpPC) { + const T &RHS = S.Stk.pop<T>(); + const T &LHS = S.Stk.pop<T>(); + const unsigned Bits = RHS.bitWidth() + 1; + return AddSubMulHelper<T, T::add, std::plus>(S, OpPC, Bits, LHS, RHS); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Sub(InterpState &S, CodePtr OpPC) { + const T &RHS = S.Stk.pop<T>(); + const T &LHS = S.Stk.pop<T>(); + const unsigned Bits = RHS.bitWidth() + 1; + return AddSubMulHelper<T, T::sub, std::minus>(S, OpPC, Bits, LHS, RHS); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Mul(InterpState &S, CodePtr OpPC) { + const T &RHS = S.Stk.pop<T>(); + const T &LHS = S.Stk.pop<T>(); + const unsigned Bits = RHS.bitWidth() * 2; + return AddSubMulHelper<T, T::mul, std::multiplies>(S, OpPC, Bits, LHS, RHS); +} + +//===----------------------------------------------------------------------===// +// EQ, NE, GT, GE, LT, LE +//===----------------------------------------------------------------------===// + +using CompareFn = llvm::function_ref<bool(ComparisonCategoryResult)>; + +template <typename T> +bool CmpHelper(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv<PT_Bool>::T; + const T &RHS = S.Stk.pop<T>(); + const T &LHS = S.Stk.pop<T>(); + S.Stk.push<BoolT>(BoolT::from(Fn(LHS.compare(RHS)))); + return true; +} + +template <typename T> +bool CmpHelperEQ(InterpState &S, CodePtr OpPC, CompareFn Fn) { + return CmpHelper<T>(S, OpPC, Fn); +} + +template <> +inline bool CmpHelper<Pointer>(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv<PT_Bool>::T; + const Pointer &RHS = S.Stk.pop<Pointer>(); + const Pointer &LHS = S.Stk.pop<Pointer>(); + + if (!Pointer::hasSameBase(LHS, RHS)) { + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.FFDiag(Loc, diag::note_invalid_subexpr_in_const_expr); + return false; + } else { + unsigned VL = LHS.getByteOffset(); + unsigned VR = RHS.getByteOffset(); + S.Stk.push<BoolT>(BoolT::from(Fn(Compare(VL, VR)))); + return true; + } +} + +template <> +inline bool CmpHelperEQ<Pointer>(InterpState &S, CodePtr OpPC, CompareFn Fn) { + using BoolT = PrimConv<PT_Bool>::T; + const Pointer &RHS = S.Stk.pop<Pointer>(); + const Pointer &LHS = S.Stk.pop<Pointer>(); + + if (LHS.isZero() || RHS.isZero()) { + if (LHS.isZero() && RHS.isZero()) + S.Stk.push<BoolT>(BoolT::from(Fn(ComparisonCategoryResult::Equal))); + else + S.Stk.push<BoolT>(BoolT::from(Fn(ComparisonCategoryResult::Nonequal))); + return true; + } + + if (!Pointer::hasSameBase(LHS, RHS)) { + S.Stk.push<BoolT>(BoolT::from(Fn(ComparisonCategoryResult::Unordered))); + return true; + } else { + unsigned VL = LHS.getByteOffset(); + unsigned VR = RHS.getByteOffset(); + S.Stk.push<BoolT>(BoolT::from(Fn(Compare(VL, VR)))); + return true; + } +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool EQ(InterpState &S, CodePtr OpPC) { + return CmpHelperEQ<T>(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Equal; + }); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool NE(InterpState &S, CodePtr OpPC) { + return CmpHelperEQ<T>(S, OpPC, [](ComparisonCategoryResult R) { + return R != ComparisonCategoryResult::Equal; + }); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool LT(InterpState &S, CodePtr OpPC) { + return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Less; + }); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool LE(InterpState &S, CodePtr OpPC) { + return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Less || + R == ComparisonCategoryResult::Equal; + }); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GT(InterpState &S, CodePtr OpPC) { + return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Greater; + }); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GE(InterpState &S, CodePtr OpPC) { + return CmpHelper<T>(S, OpPC, [](ComparisonCategoryResult R) { + return R == ComparisonCategoryResult::Greater || + R == ComparisonCategoryResult::Equal; + }); +} + +//===----------------------------------------------------------------------===// +// InRange +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InRange(InterpState &S, CodePtr OpPC) { + const T RHS = S.Stk.pop<T>(); + const T LHS = S.Stk.pop<T>(); + const T Value = S.Stk.pop<T>(); + + S.Stk.push<bool>(LHS <= Value && Value <= RHS); + return true; +} + +//===----------------------------------------------------------------------===// +// Dup, Pop, Test +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Dup(InterpState &S, CodePtr OpPC) { + S.Stk.push<T>(S.Stk.peek<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Pop(InterpState &S, CodePtr OpPC) { + S.Stk.pop<T>(); + return true; +} + +//===----------------------------------------------------------------------===// +// Const +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Const(InterpState &S, CodePtr OpPC, const T &Arg) { + S.Stk.push<T>(Arg); + return true; +} + +//===----------------------------------------------------------------------===// +// Get/Set Local/Param/Global/This +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GetLocal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Stk.push<T>(S.Current->getLocal<T>(I)); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool SetLocal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->setLocal<T>(I, S.Stk.pop<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GetParam(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) { + return false; + } + S.Stk.push<T>(S.Current->getParam<T>(I)); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool SetParam(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->setParam<T>(I, S.Stk.pop<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GetField(InterpState &S, CodePtr OpPC, uint32_t I) { + const Pointer &Obj = S.Stk.peek<Pointer>(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + if (!CheckRange(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckLoad(S, OpPC, Field)) + return false; + S.Stk.push<T>(Field.deref<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool SetField(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Obj = S.Stk.peek<Pointer>(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + if (!CheckRange(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckStore(S, OpPC, Field)) + return false; + Field.deref<T>() = Value; + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GetFieldPop(InterpState &S, CodePtr OpPC, uint32_t I) { + const Pointer &Obj = S.Stk.pop<Pointer>(); + if (!CheckNull(S, OpPC, Obj, CSK_Field)) + return false; + if (!CheckRange(S, OpPC, Obj, CSK_Field)) + return false; + const Pointer &Field = Obj.atField(I); + if (!CheckLoad(S, OpPC, Field)) + return false; + S.Stk.push<T>(Field.deref<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GetThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!CheckThis(S, OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + if (!CheckLoad(S, OpPC, Field)) + return false; + S.Stk.push<T>(Field.deref<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool SetThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const T &Value = S.Stk.pop<T>(); + const Pointer &This = S.Current->getThis(); + if (!CheckThis(S, OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + if (!CheckStore(S, OpPC, Field)) + return false; + Field.deref<T>() = Value; + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool GetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + auto *B = S.P.getGlobal(I); + if (B->isExtern()) + return false; + S.Stk.push<T>(B->deref<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool SetGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + // TODO: emit warning. + return false; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.P.getGlobal(I)->deref<T>() = S.Stk.pop<T>(); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitThisField(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!CheckThis(S, OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + Field.deref<T>() = S.Stk.pop<T>(); + Field.initialize(); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitThisBitField(InterpState &S, CodePtr OpPC, const Record::Field *F) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!CheckThis(S, OpPC, This)) + return false; + const Pointer &Field = This.atField(F->Offset); + const auto &Value = S.Stk.pop<T>(); + Field.deref<T>() = Value.truncate(F->Decl->getBitWidthValue(S.getCtx())); + Field.initialize(); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitThisFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) + return false; + const Pointer &This = S.Current->getThis(); + if (!CheckThis(S, OpPC, This)) + return false; + const Pointer &Field = This.atField(I); + Field.deref<T>() = S.Stk.pop<T>(); + Field.activate(); + Field.initialize(); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitField(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Field = S.Stk.pop<Pointer>().atField(I); + Field.deref<T>() = Value; + Field.activate(); + Field.initialize(); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitBitField(InterpState &S, CodePtr OpPC, const Record::Field *F) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Field = S.Stk.pop<Pointer>().atField(F->Offset); + Field.deref<T>() = Value.truncate(F->Decl->getBitWidthValue(S.getCtx())); + Field.activate(); + Field.initialize(); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitFieldActive(InterpState &S, CodePtr OpPC, uint32_t I) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.pop<Pointer>(); + const Pointer &Field = Ptr.atField(I); + Field.deref<T>() = 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<Pointer>(S.Current->getLocalPointer(I)); + return true; +} + +inline bool GetPtrParam(InterpState &S, CodePtr OpPC, uint32_t I) { + if (S.checkingPotentialConstantExpression()) { + return false; + } + S.Stk.push<Pointer>(S.Current->getParamPointer(I)); + return true; +} + +inline bool GetPtrGlobal(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Stk.push<Pointer>(S.P.getPtrGlobal(I)); + return true; +} + +inline bool GetPtrField(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckNull(S, OpPC, Ptr, CSK_Field)) + return false; + if (!CheckExtern(S, OpPC, Ptr)) + return false; + if (!CheckRange(S, OpPC, Ptr, CSK_Field)) + return false; + S.Stk.push<Pointer>(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 (!CheckThis(S, OpPC, This)) + return false; + S.Stk.push<Pointer>(This.atField(Off)); + return true; +} + +inline bool GetPtrActiveField(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckNull(S, OpPC, Ptr, CSK_Field)) + return false; + if (!CheckRange(S, OpPC, Ptr, CSK_Field)) + return false; + Pointer Field = Ptr.atField(Off); + Ptr.deactivate(); + Field.activate(); + S.Stk.push<Pointer>(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 (!CheckThis(S, OpPC, This)) + return false; + Pointer Field = This.atField(Off); + This.deactivate(); + Field.activate(); + S.Stk.push<Pointer>(std::move(Field)); + return true; +} + +inline bool GetPtrBase(InterpState &S, CodePtr OpPC, uint32_t Off) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckNull(S, OpPC, Ptr, CSK_Base)) + return false; + S.Stk.push<Pointer>(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 (!CheckThis(S, OpPC, This)) + return false; + S.Stk.push<Pointer>(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<Pointer>(Base.atField(Field->Offset)); + return true; +} + +inline bool GetPtrVirtBase(InterpState &S, CodePtr OpPC, const RecordDecl *D) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckNull(S, 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 (!CheckThis(S, OpPC, This)) + return false; + return VirtBaseHelper(S, OpPC, D, S.Current->getThis()); +} + +//===----------------------------------------------------------------------===// +// Load, Store, Init +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Load(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.peek<Pointer>(); + if (!CheckLoad(S, OpPC, Ptr)) + return false; + S.Stk.push<T>(Ptr.deref<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool LoadPop(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckLoad(S, OpPC, Ptr)) + return false; + S.Stk.push<T>(Ptr.deref<T>()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Store(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.peek<Pointer>(); + if (!CheckStore(S, OpPC, Ptr)) + return false; + Ptr.deref<T>() = Value; + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool StorePop(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckStore(S, OpPC, Ptr)) + return false; + Ptr.deref<T>() = Value; + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool StoreBitField(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.peek<Pointer>(); + if (!CheckStore(S, OpPC, Ptr)) + return false; + if (auto *FD = Ptr.getField()) { + Ptr.deref<T>() = Value.truncate(FD->getBitWidthValue(S.getCtx())); + } else { + Ptr.deref<T>() = Value; + } + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool StoreBitFieldPop(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckStore(S, OpPC, Ptr)) + return false; + if (auto *FD = Ptr.getField()) { + Ptr.deref<T>() = Value.truncate(FD->getBitWidthValue(S.getCtx())); + } else { + Ptr.deref<T>() = Value; + } + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitPop(InterpState &S, CodePtr OpPC) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckInit(S, OpPC, Ptr)) + return false; + Ptr.initialize(); + new (&Ptr.deref<T>()) T(Value); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitElem(InterpState &S, CodePtr OpPC, uint32_t Idx) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.peek<Pointer>().atIndex(Idx); + if (!CheckInit(S, OpPC, Ptr)) + return false; + Ptr.initialize(); + new (&Ptr.deref<T>()) T(Value); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool InitElemPop(InterpState &S, CodePtr OpPC, uint32_t Idx) { + const T &Value = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.pop<Pointer>().atIndex(Idx); + if (!CheckInit(S, OpPC, Ptr)) + return false; + Ptr.initialize(); + new (&Ptr.deref<T>()) T(Value); + return true; +} + +//===----------------------------------------------------------------------===// +// AddOffset, SubOffset +//===----------------------------------------------------------------------===// + +template <class T, bool Add> bool OffsetHelper(InterpState &S, CodePtr OpPC) { + // Fetch the pointer and the offset. + const T &Offset = S.Stk.pop<T>(); + const Pointer &Ptr = S.Stk.pop<Pointer>(); + if (!CheckNull(S, OpPC, Ptr, CSK_ArrayIndex)) + return false; + if (!CheckRange(S, 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<Pointer>(Index.isZero() ? Ptr.atIndex(0) : Ptr); + return true; + } + // Arrays of unknown bounds cannot have pointers into them. + if (!CheckArray(S, 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.Current->getSource(OpPC), diag::note_constexpr_array_index) + << NewIndex + << /*array*/ static_cast<int>(!Ptr.inArray()) + << static_cast<unsigned>(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<int64_t>(Index); + int64_t WideOffset = static_cast<int64_t>(Offset); + int64_t Result = Add ? (WideIndex + WideOffset) : (WideIndex - WideOffset); + S.Stk.push<Pointer>(Ptr.atIndex(static_cast<unsigned>(Result))); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool AddOffset(InterpState &S, CodePtr OpPC) { + return OffsetHelper<T, true>(S, OpPC); +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool SubOffset(InterpState &S, CodePtr OpPC) { + return OffsetHelper<T, false>(S, OpPC); +} + + +//===----------------------------------------------------------------------===// +// Destroy +//===----------------------------------------------------------------------===// + +inline bool Destroy(InterpState &S, CodePtr OpPC, uint32_t I) { + S.Current->destroy(I); + return true; +} + +//===----------------------------------------------------------------------===// +// Cast, CastFP +//===----------------------------------------------------------------------===// + +template <PrimType TIn, PrimType TOut> bool Cast(InterpState &S, CodePtr OpPC) { + using T = typename PrimConv<TIn>::T; + using U = typename PrimConv<TOut>::T; + S.Stk.push<U>(U::from(S.Stk.pop<T>())); + return true; +} + +//===----------------------------------------------------------------------===// +// Zero, Nullptr +//===----------------------------------------------------------------------===// + +template <PrimType Name, class T = typename PrimConv<Name>::T> +bool Zero(InterpState &S, CodePtr OpPC) { + S.Stk.push<T>(T::zero()); + return true; +} + +template <PrimType Name, class T = typename PrimConv<Name>::T> +inline bool Null(InterpState &S, CodePtr OpPC) { + S.Stk.push<T>(); + return true; +} + +//===----------------------------------------------------------------------===// +// This, ImplicitThis +//===----------------------------------------------------------------------===// + +inline bool This(InterpState &S, CodePtr OpPC) { + // Cannot read 'this' in this mode. + if (S.checkingPotentialConstantExpression()) { + return false; + } + + const Pointer &This = S.Current->getThis(); + if (!CheckThis(S, OpPC, This)) + return false; + + S.Stk.push<Pointer>(This); + return true; +} + +//===----------------------------------------------------------------------===// +// Shr, Shl +//===----------------------------------------------------------------------===// + +template <PrimType TR, PrimType TL, class T = typename PrimConv<TR>::T> +unsigned Trunc(InterpState &S, CodePtr OpPC, unsigned Bits, const T &V) { + // C++11 [expr.shift]p1: Shift width must be less than the bit width of + // the shifted type. + if (Bits > 1 && V >= T::from(Bits, V.bitWidth())) { + const Expr *E = S.Current->getExpr(OpPC); + const APSInt Val = V.toAPSInt(); + QualType Ty = E->getType(); + S.CCEDiag(E, diag::note_constexpr_large_shift) << Val << Ty << Bits; + return Bits; + } else { + return static_cast<unsigned>(V); + } +} + +template <PrimType TL, PrimType TR, typename T = typename PrimConv<TL>::T> +inline bool ShiftRight(InterpState &S, CodePtr OpPC, const T &V, unsigned RHS) { + if (RHS >= V.bitWidth()) { + S.Stk.push<T>(T::from(0, V.bitWidth())); + } else { + S.Stk.push<T>(T::from(V >> RHS, V.bitWidth())); + } + return true; +} + +template <PrimType TL, PrimType TR, typename T = typename PrimConv<TL>::T> +inline bool ShiftLeft(InterpState &S, CodePtr OpPC, const T &V, unsigned RHS) { + if (V.isSigned() && !S.getLangOpts().CPlusPlus2a) { + // C++11 [expr.shift]p2: A signed left shift must have a non-negative + // operand, and must not overflow the corresponding unsigned type. + // C++2a [expr.shift]p2: E1 << E2 is the unique value congruent to + // E1 x 2^E2 module 2^N. + if (V.isNegative()) { + const Expr *E = S.Current->getExpr(OpPC); + S.CCEDiag(E, diag::note_constexpr_lshift_of_negative) << V.toAPSInt(); + } else if (V.countLeadingZeros() < RHS) { + S.CCEDiag(S.Current->getExpr(OpPC), diag::note_constexpr_lshift_discards); + } + } + + if (V.bitWidth() == 1) { + S.Stk.push<T>(V); + } else if (RHS >= V.bitWidth()) { + S.Stk.push<T>(T::from(0, V.bitWidth())); + } else { + S.Stk.push<T>(T::from(V.toUnsigned() << RHS, V.bitWidth())); + } + return true; +} + +template <PrimType TL, PrimType TR> +inline bool Shr(InterpState &S, CodePtr OpPC) { + const auto &RHS = S.Stk.pop<typename PrimConv<TR>::T>(); + const auto &LHS = S.Stk.pop<typename PrimConv<TL>::T>(); + const unsigned Bits = LHS.bitWidth(); + + if (RHS.isSigned() && RHS.isNegative()) { + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt(); + return ShiftLeft<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, -RHS)); + } else { + return ShiftRight<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, RHS)); + } +} + +template <PrimType TL, PrimType TR> +inline bool Shl(InterpState &S, CodePtr OpPC) { + const auto &RHS = S.Stk.pop<typename PrimConv<TR>::T>(); + const auto &LHS = S.Stk.pop<typename PrimConv<TL>::T>(); + const unsigned Bits = LHS.bitWidth(); + + if (RHS.isSigned() && RHS.isNegative()) { + const SourceInfo &Loc = S.Current->getSource(OpPC); + S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt(); + return ShiftRight<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, -RHS)); + } else { + return ShiftLeft<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, RHS)); + } +} + +//===----------------------------------------------------------------------===// +// NoRet +//===----------------------------------------------------------------------===// + +inline bool NoRet(InterpState &S, CodePtr OpPC) { + SourceLocation EndLoc = S.Current->getCallee()->getEndLoc(); + S.FFDiag(EndLoc, diag::note_constexpr_no_return); + return false; +} + +//===----------------------------------------------------------------------===// +// NarrowPtr, ExpandPtr +//===----------------------------------------------------------------------===// + +inline bool NarrowPtr(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + S.Stk.push<Pointer>(Ptr.narrow()); + return true; +} + +inline bool ExpandPtr(InterpState &S, CodePtr OpPC) { + const Pointer &Ptr = S.Stk.pop<Pointer>(); + S.Stk.push<Pointer>(Ptr.expand()); + return true; +} + +/// Interpreter entry point. +bool Interpret(InterpState &S, APValue &Result); + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/InterpFrame.cpp b/clang/lib/AST/Interp/InterpFrame.cpp new file mode 100644 index 000000000000..9d01bf0333fe --- /dev/null +++ b/clang/lib/AST/Interp/InterpFrame.cpp @@ -0,0 +1,193 @@ +//===--- InterpFrame.cpp - Call Frame implementation for the VM -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "InterpFrame.h" +#include "Function.h" +#include "Interp.h" +#include "InterpStack.h" +#include "PrimType.h" +#include "Program.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +InterpFrame::InterpFrame(InterpState &S, Function *Func, InterpFrame *Caller, + CodePtr RetPC, Pointer &&This) + : Caller(Caller), S(S), Func(Func), This(std::move(This)), RetPC(RetPC), + ArgSize(Func ? Func->getArgSize() : 0), + Args(static_cast<char *>(S.Stk.top())), FrameOffset(S.Stk.size()) { + if (Func) { + if (unsigned FrameSize = Func->getFrameSize()) { + Locals = std::make_unique<char[]>(FrameSize); + for (auto &Scope : Func->scopes()) { + for (auto &Local : Scope.locals()) { + Block *B = new (localBlock(Local.Offset)) Block(Local.Desc); + B->invokeCtor(); + } + } + } + } +} + +InterpFrame::~InterpFrame() { + if (Func && Func->isConstructor() && This.isBaseClass()) + This.initialize(); + for (auto &Param : Params) + S.deallocate(reinterpret_cast<Block *>(Param.second.get())); +} + +void InterpFrame::destroy(unsigned Idx) { + for (auto &Local : Func->getScope(Idx).locals()) { + S.deallocate(reinterpret_cast<Block *>(localBlock(Local.Offset))); + } +} + +void InterpFrame::popArgs() { + for (PrimType Ty : Func->args_reverse()) + TYPE_SWITCH(Ty, S.Stk.discard<T>()); +} + +template <typename T> +static void print(llvm::raw_ostream &OS, const T &V, ASTContext &, QualType) { + OS << V; +} + +template <> +void print(llvm::raw_ostream &OS, const Pointer &P, ASTContext &Ctx, + QualType Ty) { + if (P.isZero()) { + OS << "nullptr"; + return; + } + + auto printDesc = [&OS, &Ctx](Descriptor *Desc) { + if (auto *D = Desc->asDecl()) { + // Subfields or named values. + if (auto *VD = dyn_cast<ValueDecl>(D)) { + OS << *VD; + return; + } + // Base classes. + if (isa<RecordDecl>(D)) { + return; + } + } + // Temporary expression. + if (auto *E = Desc->asExpr()) { + E->printPretty(OS, nullptr, Ctx.getPrintingPolicy()); + return; + } + llvm_unreachable("Invalid descriptor type"); + }; + + if (!Ty->isReferenceType()) + OS << "&"; + llvm::SmallVector<Pointer, 2> Levels; + for (Pointer F = P; !F.isRoot(); ) { + Levels.push_back(F); + F = F.isArrayElement() ? F.getArray().expand() : F.getBase(); + } + + printDesc(P.getDeclDesc()); + for (auto It = Levels.rbegin(); It != Levels.rend(); ++It) { + if (It->inArray()) { + OS << "[" << It->expand().getIndex() << "]"; + continue; + } + if (auto Index = It->getIndex()) { + OS << " + " << Index; + continue; + } + OS << "."; + printDesc(It->getFieldDesc()); + } +} + +void InterpFrame::describe(llvm::raw_ostream &OS) { + const FunctionDecl *F = getCallee(); + auto *M = dyn_cast<CXXMethodDecl>(F); + if (M && M->isInstance() && !isa<CXXConstructorDecl>(F)) { + print(OS, This, S.getCtx(), S.getCtx().getRecordType(M->getParent())); + OS << "->"; + } + OS << *F << "("; + unsigned Off = Func->hasRVO() ? primSize(PT_Ptr) : 0; + for (unsigned I = 0, N = F->getNumParams(); I < N; ++I) { + QualType Ty = F->getParamDecl(I)->getType(); + + PrimType PrimTy; + if (llvm::Optional<PrimType> T = S.Ctx.classify(Ty)) { + PrimTy = *T; + } else { + PrimTy = PT_Ptr; + } + + TYPE_SWITCH(PrimTy, print(OS, stackRef<T>(Off), S.getCtx(), Ty)); + Off += align(primSize(PrimTy)); + if (I + 1 != N) + OS << ", "; + } + OS << ")"; +} + +Frame *InterpFrame::getCaller() const { + if (Caller->Caller) + return Caller; + return S.getSplitFrame(); +} + +SourceLocation InterpFrame::getCallLocation() const { + if (!Caller->Func) + return S.getLocation(nullptr, {}); + return S.getLocation(Caller->Func, RetPC - sizeof(uintptr_t)); +} + +const FunctionDecl *InterpFrame::getCallee() const { + return Func->getDecl(); +} + +Pointer InterpFrame::getLocalPointer(unsigned Offset) { + assert(Offset < Func->getFrameSize() && "Invalid local offset."); + return Pointer( + reinterpret_cast<Block *>(Locals.get() + Offset - sizeof(Block))); +} + +Pointer InterpFrame::getParamPointer(unsigned Off) { + // Return the block if it was created previously. + auto Pt = Params.find(Off); + if (Pt != Params.end()) { + return Pointer(reinterpret_cast<Block *>(Pt->second.get())); + } + + // Allocate memory to store the parameter and the block metadata. + const auto &Desc = Func->getParamDescriptor(Off); + size_t BlockSize = sizeof(Block) + Desc.second->getAllocSize(); + auto Memory = std::make_unique<char[]>(BlockSize); + auto *B = new (Memory.get()) Block(Desc.second); + + // Copy the initial value. + TYPE_SWITCH(Desc.first, new (B->data()) T(stackRef<T>(Off))); + + // Record the param. + Params.insert({Off, std::move(Memory)}); + return Pointer(B); +} + +SourceInfo InterpFrame::getSource(CodePtr PC) const { + return S.getSource(Func, PC); +} + +const Expr *InterpFrame::getExpr(CodePtr PC) const { + return S.getExpr(Func, PC); +} + +SourceLocation InterpFrame::getLocation(CodePtr PC) const { + return S.getLocation(Func, PC); +} + diff --git a/clang/lib/AST/Interp/InterpFrame.h b/clang/lib/AST/Interp/InterpFrame.h new file mode 100644 index 000000000000..b8391b0bcf92 --- /dev/null +++ b/clang/lib/AST/Interp/InterpFrame.h @@ -0,0 +1,153 @@ +//===--- InterpFrame.h - Call Frame implementation for the VM ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the class storing information about stack frames in the interpreter. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERPFRAME_H +#define LLVM_CLANG_AST_INTERP_INTERPFRAME_H + +#include "Frame.h" +#include "Pointer.h" +#include "Program.h" +#include "State.h" +#include <cstdint> +#include <vector> + +namespace clang { +namespace interp { +class Function; +class InterpState; + +/// Frame storing local variables. +class InterpFrame final : public Frame { +public: + /// The frame of the previous function. + InterpFrame *Caller; + + /// Creates a new frame for a method call. + InterpFrame(InterpState &S, Function *Func, InterpFrame *Caller, + CodePtr RetPC, Pointer &&This); + + /// Destroys the frame, killing all live pointers to stack slots. + ~InterpFrame(); + + /// Invokes the destructors for a scope. + void destroy(unsigned Idx); + + /// Pops the arguments off the stack. + void popArgs(); + + /// Describes the frame with arguments for diagnostic purposes. + void describe(llvm::raw_ostream &OS); + + /// Returns the parent frame object. + Frame *getCaller() const; + + /// Returns the location of the call to the frame. + SourceLocation getCallLocation() const; + + /// Returns the caller. + const FunctionDecl *getCallee() const; + + /// Returns the current function. + Function *getFunction() const { return Func; } + + /// Returns the offset on the stack at which the frame starts. + size_t getFrameOffset() const { return FrameOffset; } + + /// Returns the value of a local variable. + template <typename T> const T &getLocal(unsigned Offset) { + return localRef<T>(Offset); + } + + /// Mutates a local variable. + template <typename T> void setLocal(unsigned Offset, const T &Value) { + localRef<T>(Offset) = Value; + } + + /// Returns a pointer to a local variables. + Pointer getLocalPointer(unsigned Offset); + + /// Returns the value of an argument. + template <typename T> const T &getParam(unsigned Offset) { + auto Pt = Params.find(Offset); + if (Pt == Params.end()) { + return stackRef<T>(Offset); + } else { + return Pointer(reinterpret_cast<Block *>(Pt->second.get())).deref<T>(); + } + } + + /// Mutates a local copy of a parameter. + template <typename T> void setParam(unsigned Offset, const T &Value) { + getParamPointer(Offset).deref<T>() = Value; + } + + /// Returns a pointer to an argument - lazily creates a block. + Pointer getParamPointer(unsigned Offset); + + /// Returns the 'this' pointer. + const Pointer &getThis() const { return This; } + + /// Checks if the frame is a root frame - return should quit the interpreter. + bool isRoot() const { return !Func; } + + /// Returns the PC of the frame's code start. + CodePtr getPC() const { return Func->getCodeBegin(); } + + /// Returns the return address of the frame. + CodePtr getRetPC() const { return RetPC; } + + /// Map a location to a source. + virtual SourceInfo getSource(CodePtr PC) const; + const Expr *getExpr(CodePtr PC) const; + SourceLocation getLocation(CodePtr PC) const; + +private: + /// Returns an original argument from the stack. + template <typename T> const T &stackRef(unsigned Offset) { + return *reinterpret_cast<const T *>(Args - ArgSize + Offset); + } + + /// Returns an offset to a local. + template <typename T> T &localRef(unsigned Offset) { + return *reinterpret_cast<T *>(Locals.get() + Offset); + } + + /// Returns a pointer to a local's block. + void *localBlock(unsigned Offset) { + return Locals.get() + Offset - sizeof(Block); + } + +private: + /// Reference to the interpreter state. + InterpState &S; + /// Reference to the function being executed. + Function *Func; + /// Current object pointer for methods. + Pointer This; + /// Return address. + CodePtr RetPC; + /// The size of all the arguments. + const unsigned ArgSize; + /// Pointer to the arguments in the callee's frame. + char *Args = nullptr; + /// Fixed, initial storage for known local variables. + std::unique_ptr<char[]> Locals; + /// Offset on the stack at entry. + const size_t FrameOffset; + /// Mapping from arg offsets to their argument blocks. + llvm::DenseMap<unsigned, std::unique_ptr<char[]>> Params; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/InterpStack.cpp b/clang/lib/AST/Interp/InterpStack.cpp new file mode 100644 index 000000000000..5c803f3d9424 --- /dev/null +++ b/clang/lib/AST/Interp/InterpStack.cpp @@ -0,0 +1,78 @@ +//===--- InterpStack.cpp - Stack implementation for the VM ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include <cassert> +#include <cstdlib> +#include "InterpStack.h" + +using namespace clang; +using namespace clang::interp; + +InterpStack::~InterpStack() { + clear(); +} + +void InterpStack::clear() { + if (Chunk && Chunk->Next) + free(Chunk->Next); + if (Chunk) + free(Chunk); + Chunk = nullptr; + StackSize = 0; +} + +void *InterpStack::grow(size_t Size) { + assert(Size < ChunkSize - sizeof(StackChunk) && "Object too large"); + + if (!Chunk || sizeof(StackChunk) + Chunk->size() + Size > ChunkSize) { + if (Chunk && Chunk->Next) { + Chunk = Chunk->Next; + } else { + StackChunk *Next = new (malloc(ChunkSize)) StackChunk(Chunk); + if (Chunk) + Chunk->Next = Next; + Chunk = Next; + } + } + + auto *Object = reinterpret_cast<void *>(Chunk->End); + Chunk->End += Size; + StackSize += Size; + return Object; +} + +void *InterpStack::peek(size_t Size) { + assert(Chunk && "Stack is empty!"); + + StackChunk *Ptr = Chunk; + while (Size > Ptr->size()) { + Size -= Ptr->size(); + Ptr = Ptr->Prev; + assert(Ptr && "Offset too large"); + } + + return reinterpret_cast<void *>(Ptr->End - Size); +} + +void InterpStack::shrink(size_t Size) { + assert(Chunk && "Chunk is empty!"); + + while (Size > Chunk->size()) { + Size -= Chunk->size(); + if (Chunk->Next) { + free(Chunk->Next); + Chunk->Next = nullptr; + } + Chunk->End = Chunk->start(); + Chunk = Chunk->Prev; + assert(Chunk && "Offset too large"); + } + + Chunk->End -= Size; + StackSize -= Size; +} diff --git a/clang/lib/AST/Interp/InterpStack.h b/clang/lib/AST/Interp/InterpStack.h new file mode 100644 index 000000000000..127adb6b8eba --- /dev/null +++ b/clang/lib/AST/Interp/InterpStack.h @@ -0,0 +1,113 @@ +//===--- InterpStack.h - Stack implementation for the VM --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the upwards-growing stack used by the interpreter. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H +#define LLVM_CLANG_AST_INTERP_INTERPSTACK_H + +#include <memory> + +namespace clang { +namespace interp { + +/// Stack frame storing temporaries and parameters. +class InterpStack final { +public: + InterpStack() {} + + /// Destroys the stack, freeing up storage. + ~InterpStack(); + + /// Constructs a value in place on the top of the stack. + template <typename T, typename... Tys> void push(Tys &&... Args) { + new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...); + } + + /// Returns the value from the top of the stack and removes it. + template <typename T> T pop() { + auto *Ptr = &peek<T>(); + auto Value = std::move(*Ptr); + Ptr->~T(); + shrink(aligned_size<T>()); + return Value; + } + + /// Discards the top value from the stack. + template <typename T> void discard() { + auto *Ptr = &peek<T>(); + Ptr->~T(); + shrink(aligned_size<T>()); + } + + /// Returns a reference to the value on the top of the stack. + template <typename T> T &peek() { + return *reinterpret_cast<T *>(peek(aligned_size<T>())); + } + + /// Returns a pointer to the top object. + void *top() { return Chunk ? peek(0) : nullptr; } + + /// Returns the size of the stack in bytes. + size_t size() const { return StackSize; } + + /// Clears the stack without calling any destructors. + void clear(); + +private: + /// All stack slots are aligned to the native pointer alignment for storage. + /// The size of an object is rounded up to a pointer alignment multiple. + template <typename T> constexpr size_t aligned_size() const { + constexpr size_t PtrAlign = alignof(void *); + return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign; + } + + /// Grows the stack to accomodate a value and returns a pointer to it. + void *grow(size_t Size); + /// Returns a pointer from the top of the stack. + void *peek(size_t Size); + /// Shrinks the stack. + void shrink(size_t Size); + + /// Allocate stack space in 1Mb chunks. + static constexpr size_t ChunkSize = 1024 * 1024; + + /// Metadata for each stack chunk. + /// + /// The stack is composed of a linked list of chunks. Whenever an allocation + /// is out of bounds, a new chunk is linked. When a chunk becomes empty, + /// it is not immediately freed: a chunk is deallocated only when the + /// predecessor becomes empty. + struct StackChunk { + StackChunk *Next; + StackChunk *Prev; + char *End; + + StackChunk(StackChunk *Prev = nullptr) + : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {} + + /// Returns the size of the chunk, minus the header. + size_t size() { return End - start(); } + + /// Returns a pointer to the start of the data region. + char *start() { return reinterpret_cast<char *>(this + 1); } + }; + static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size"); + + /// First chunk on the stack. + StackChunk *Chunk = nullptr; + /// Total size of the stack. + size_t StackSize = 0; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/InterpState.cpp b/clang/lib/AST/Interp/InterpState.cpp new file mode 100644 index 000000000000..25684f3c0939 --- /dev/null +++ b/clang/lib/AST/Interp/InterpState.cpp @@ -0,0 +1,74 @@ +//===--- InterpState.cpp - Interpreter for the constexpr VM -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "InterpState.h" +#include <limits> +#include "Function.h" +#include "InterpFrame.h" +#include "InterpStack.h" +#include "Opcode.h" +#include "PrimType.h" +#include "Program.h" +#include "State.h" + +using namespace clang; +using namespace clang::interp; + +using APSInt = llvm::APSInt; + +InterpState::InterpState(State &Parent, Program &P, InterpStack &Stk, + Context &Ctx, SourceMapper *M) + : Parent(Parent), M(M), P(P), Stk(Stk), Ctx(Ctx), Current(nullptr), + CallStackDepth(Parent.getCallStackDepth() + 1) {} + +InterpState::~InterpState() { + while (Current) { + InterpFrame *Next = Current->Caller; + delete Current; + Current = Next; + } + + while (DeadBlocks) { + DeadBlock *Next = DeadBlocks->Next; + free(DeadBlocks); + DeadBlocks = Next; + } +} + +Frame *InterpState::getCurrentFrame() { + if (Current && Current->Caller) { + return Current; + } else { + return Parent.getCurrentFrame(); + } +} + +bool InterpState::reportOverflow(const Expr *E, const llvm::APSInt &Value) { + QualType Type = E->getType(); + CCEDiag(E, diag::note_constexpr_overflow) << Value << Type; + return noteUndefinedBehavior(); +} + +void InterpState::deallocate(Block *B) { + Descriptor *Desc = B->getDescriptor(); + if (B->hasPointers()) { + size_t Size = B->getSize(); + + // Allocate a new block, transferring over pointers. + char *Memory = reinterpret_cast<char *>(malloc(sizeof(DeadBlock) + Size)); + auto *D = new (Memory) DeadBlock(DeadBlocks, B); + + // Move data from one block to another. + if (Desc->MoveFn) + Desc->MoveFn(B, B->data(), D->data(), Desc); + } else { + // Free storage, if necessary. + if (Desc->DtorFn) + Desc->DtorFn(B, B->data(), Desc); + } +} diff --git a/clang/lib/AST/Interp/InterpState.h b/clang/lib/AST/Interp/InterpState.h new file mode 100644 index 000000000000..c2209bbcbb92 --- /dev/null +++ b/clang/lib/AST/Interp/InterpState.h @@ -0,0 +1,112 @@ +//===--- InterpState.h - Interpreter state for the constexpr VM -*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Definition of the interpreter state and entry point. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_INTERPSTATE_H +#define LLVM_CLANG_AST_INTERP_INTERPSTATE_H + +#include "Context.h" +#include "Function.h" +#include "InterpStack.h" +#include "State.h" +#include "clang/AST/APValue.h" +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/Expr.h" +#include "clang/AST/OptionalDiagnostic.h" + +namespace clang { +namespace interp { +class Context; +class Function; +class InterpStack; +class InterpFrame; +class SourceMapper; + +/// Interpreter context. +class InterpState final : public State, public SourceMapper { +public: + InterpState(State &Parent, Program &P, InterpStack &Stk, Context &Ctx, + SourceMapper *M = nullptr); + + ~InterpState(); + + // Stack frame accessors. + Frame *getSplitFrame() { return Parent.getCurrentFrame(); } + Frame *getCurrentFrame() override; + unsigned getCallStackDepth() override { return CallStackDepth; } + const Frame *getBottomFrame() const override { + return Parent.getBottomFrame(); + } + + // Acces objects from the walker context. + Expr::EvalStatus &getEvalStatus() const override { + return Parent.getEvalStatus(); + } + ASTContext &getCtx() const override { return Parent.getCtx(); } + + // Forward status checks and updates to the walker. + bool checkingForUndefinedBehavior() const override { + return Parent.checkingForUndefinedBehavior(); + } + bool keepEvaluatingAfterFailure() const override { + return Parent.keepEvaluatingAfterFailure(); + } + bool checkingPotentialConstantExpression() const override { + return Parent.checkingPotentialConstantExpression(); + } + bool noteUndefinedBehavior() override { + return Parent.noteUndefinedBehavior(); + } + bool hasActiveDiagnostic() override { return Parent.hasActiveDiagnostic(); } + void setActiveDiagnostic(bool Flag) override { + Parent.setActiveDiagnostic(Flag); + } + void setFoldFailureDiagnostic(bool Flag) override { + Parent.setFoldFailureDiagnostic(Flag); + } + bool hasPriorDiagnostic() override { return Parent.hasPriorDiagnostic(); } + + /// Reports overflow and return true if evaluation should continue. + bool reportOverflow(const Expr *E, const llvm::APSInt &Value); + + /// Deallocates a pointer. + void deallocate(Block *B); + + /// Delegates source mapping to the mapper. + SourceInfo getSource(Function *F, CodePtr PC) const override { + return M ? M->getSource(F, PC) : F->getSource(PC); + } + +private: + /// AST Walker state. + State &Parent; + /// Dead block chain. + DeadBlock *DeadBlocks = nullptr; + /// Reference to the offset-source mapping. + SourceMapper *M; + +public: + /// Reference to the module containing all bytecode. + Program &P; + /// Temporary stack. + InterpStack &Stk; + /// Interpreter Context. + Context &Ctx; + /// The current frame. + InterpFrame *Current = nullptr; + /// Call stack depth. + unsigned CallStackDepth; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Opcode.h b/clang/lib/AST/Interp/Opcode.h new file mode 100644 index 000000000000..d2daa1ea52ac --- /dev/null +++ b/clang/lib/AST/Interp/Opcode.h @@ -0,0 +1,30 @@ +//===--- Opcode.h - Opcodes for the constexpr VM ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines all opcodes executed by the VM and emitted by the compiler. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_OPCODE_H +#define LLVM_CLANG_AST_INTERP_OPCODE_H + +#include <cstdint> + +namespace clang { +namespace interp { + +enum Opcode : uint32_t { +#define GET_OPCODE_NAMES +#include "Opcodes.inc" +#undef GET_OPCODE_NAMES +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Opcodes.td b/clang/lib/AST/Interp/Opcodes.td new file mode 100644 index 000000000000..4aba5f5cd83c --- /dev/null +++ b/clang/lib/AST/Interp/Opcodes.td @@ -0,0 +1,422 @@ +//===--- Opcodes.td - Opcode defitions for the constexpr VM -----*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Helper file used to generate opcodes, the interpreter and the disassembler. +// +//===----------------------------------------------------------------------===// + + +//===----------------------------------------------------------------------===// +// Types evaluated by the interpreter. +//===----------------------------------------------------------------------===// + +class Type; +def Bool : Type; +def Sint8 : Type; +def Uint8 : Type; +def Sint16 : Type; +def Uint16 : Type; +def Sint32 : Type; +def Uint32 : Type; +def Sint64 : Type; +def Uint64 : Type; +def Ptr : Type; + +//===----------------------------------------------------------------------===// +// Types transferred to the interpreter. +//===----------------------------------------------------------------------===// + +class ArgType { string Name = ?; } +def ArgSint8 : ArgType { let Name = "int8_t"; } +def ArgUint8 : ArgType { let Name = "uint8_t"; } +def ArgSint16 : ArgType { let Name = "int16_t"; } +def ArgUint16 : ArgType { let Name = "uint16_t"; } +def ArgSint32 : ArgType { let Name = "int32_t"; } +def ArgUint32 : ArgType { let Name = "uint32_t"; } +def ArgSint64 : ArgType { let Name = "int64_t"; } +def ArgUint64 : ArgType { let Name = "uint64_t"; } +def ArgBool : ArgType { let Name = "bool"; } + +def ArgFunction : ArgType { let Name = "Function *"; } +def ArgRecord : ArgType { let Name = "Record *"; } + +def ArgSema : ArgType { let Name = "const fltSemantics *"; } + +def ArgExpr : ArgType { let Name = "const Expr *"; } +def ArgFloatingLiteral : ArgType { let Name = "const FloatingLiteral *"; } +def ArgCXXMethodDecl : ArgType { let Name = "const CXXMethodDecl *"; } +def ArgFunctionDecl : ArgType { let Name = "const FunctionDecl *"; } +def ArgRecordDecl : ArgType { let Name = "const RecordDecl *"; } +def ArgCXXRecordDecl : ArgType { let Name = "const CXXRecordDecl *"; } +def ArgValueDecl : ArgType { let Name = "const ValueDecl *"; } +def ArgRecordField : ArgType { let Name = "const Record::Field *"; } + +//===----------------------------------------------------------------------===// +// Classes of types intructions operate on. +//===----------------------------------------------------------------------===// + +class TypeClass { + list<Type> Types; +} + +def AluTypeClass : TypeClass { + let Types = [Sint8, Uint8, Sint16, Uint16, Sint32, + Uint32, Sint64, Uint64, Bool]; +} + +def PtrTypeClass : TypeClass { + let Types = [Ptr]; +} + +def AllTypeClass : TypeClass { + let Types = !listconcat(AluTypeClass.Types, PtrTypeClass.Types); +} + +def ComparableTypeClass : TypeClass { + let Types = !listconcat(AluTypeClass.Types, [Ptr]); +} + +class SingletonTypeClass<Type Ty> : TypeClass { + let Types = [Ty]; +} + +//===----------------------------------------------------------------------===// +// Record describing all opcodes. +//===----------------------------------------------------------------------===// + +class Opcode { + list<TypeClass> Types = []; + list<ArgType> Args = []; + string Name = ""; + bit CanReturn = 0; + bit ChangesPC = 0; + bit HasCustomLink = 0; + bit HasCustomEval = 0; + bit HasGroup = 0; +} + +class AluOpcode : Opcode { + let Types = [AluTypeClass]; + let HasGroup = 1; +} + +//===----------------------------------------------------------------------===// +// Jump opcodes +//===----------------------------------------------------------------------===// + +class JumpOpcode : Opcode { + let Args = [ArgSint32]; + let ChangesPC = 1; + let HasCustomEval = 1; +} + +// [] -> [] +def Jmp : JumpOpcode; +// [Bool] -> [], jumps if true. +def Jt : JumpOpcode; +// [Bool] -> [], jumps if false. +def Jf : JumpOpcode; + +//===----------------------------------------------------------------------===// +// Returns +//===----------------------------------------------------------------------===// + +// [Value] -> [] +def Ret : Opcode { + let Types = [AllTypeClass]; + let ChangesPC = 1; + let CanReturn = 1; + let HasGroup = 1; + let HasCustomEval = 1; +} +// [] -> [] +def RetVoid : Opcode { + let CanReturn = 1; + let ChangesPC = 1; + let HasCustomEval = 1; +} +// [Value] -> [] +def RetValue : Opcode { + let CanReturn = 1; + let ChangesPC = 1; + let HasCustomEval = 1; +} +// [] -> EXIT +def NoRet : Opcode {} + +//===----------------------------------------------------------------------===// +// Frame management +//===----------------------------------------------------------------------===// + +// [] -> [] +def Destroy : Opcode { + let Args = [ArgUint32]; + let HasCustomEval = 1; +} + +//===----------------------------------------------------------------------===// +// Constants +//===----------------------------------------------------------------------===// + +class ConstOpcode<Type Ty, ArgType ArgTy> : Opcode { + let Types = [SingletonTypeClass<Ty>]; + let Args = [ArgTy]; + let Name = "Const"; +} + +// [] -> [Integer] +def ConstSint8 : ConstOpcode<Sint8, ArgSint8>; +def ConstUint8 : ConstOpcode<Uint8, ArgUint8>; +def ConstSint16 : ConstOpcode<Sint16, ArgSint16>; +def ConstUint16 : ConstOpcode<Uint16, ArgUint16>; +def ConstSint32 : ConstOpcode<Sint32, ArgSint32>; +def ConstUint32 : ConstOpcode<Uint32, ArgUint32>; +def ConstSint64 : ConstOpcode<Sint64, ArgSint64>; +def ConstUint64 : ConstOpcode<Uint64, ArgUint64>; +def ConstBool : ConstOpcode<Bool, ArgBool>; + +// [] -> [Integer] +def Zero : Opcode { + let Types = [AluTypeClass]; +} + +// [] -> [Pointer] +def Null : Opcode { + let Types = [PtrTypeClass]; +} + +//===----------------------------------------------------------------------===// +// Pointer generation +//===----------------------------------------------------------------------===// + +// [] -> [Pointer] +def GetPtrLocal : Opcode { + // Offset of local. + let Args = [ArgUint32]; + bit HasCustomEval = 1; +} +// [] -> [Pointer] +def GetPtrParam : Opcode { + // Offset of parameter. + let Args = [ArgUint32]; +} +// [] -> [Pointer] +def GetPtrGlobal : Opcode { + // Index of global. + let Args = [ArgUint32]; +} +// [Pointer] -> [Pointer] +def GetPtrField : Opcode { + // Offset of field. + let Args = [ArgUint32]; +} +// [Pointer] -> [Pointer] +def GetPtrActiveField : Opcode { + // Offset of field. + let Args = [ArgUint32]; +} +// [] -> [Pointer] +def GetPtrActiveThisField : Opcode { + // Offset of field. + let Args = [ArgUint32]; +} +// [] -> [Pointer] +def GetPtrThisField : Opcode { + // Offset of field. + let Args = [ArgUint32]; +} +// [Pointer] -> [Pointer] +def GetPtrBase : Opcode { + // Offset of field, which is a base. + let Args = [ArgUint32]; +} +// [Pointer] -> [Pointer] +def GetPtrVirtBase : Opcode { + // RecordDecl of base class. + let Args = [ArgRecordDecl]; +} +// [] -> [Pointer] +def GetPtrThisBase : Opcode { + // Offset of field, which is a base. + let Args = [ArgUint32]; +} +// [] -> [Pointer] +def GetPtrThisVirtBase : Opcode { + // RecordDecl of base class. + let Args = [ArgRecordDecl]; +} +// [] -> [Pointer] +def This : Opcode; + +// [Pointer] -> [Pointer] +def NarrowPtr : Opcode; +// [Pointer] -> [Pointer] +def ExpandPtr : Opcode; + +//===----------------------------------------------------------------------===// +// Direct field accessors +//===----------------------------------------------------------------------===// + +class AccessOpcode : Opcode { + let Types = [AllTypeClass]; + let Args = [ArgUint32]; + let HasGroup = 1; +} + +class BitFieldOpcode : Opcode { + let Types = [AluTypeClass]; + let Args = [ArgRecordField]; + let HasGroup = 1; +} + +// [] -> [Pointer] +def GetLocal : AccessOpcode { let HasCustomEval = 1; } +// [] -> [Pointer] +def SetLocal : AccessOpcode { let HasCustomEval = 1; } + +// [] -> [Value] +def GetGlobal : AccessOpcode; +// [Value] -> [] +def InitGlobal : AccessOpcode; +// [Value] -> [] +def SetGlobal : AccessOpcode; + +// [] -> [Value] +def GetParam : AccessOpcode; +// [Value] -> [] +def SetParam : AccessOpcode; + +// [Pointer] -> [Pointer, Value] +def GetField : AccessOpcode; +// [Pointer] -> [Value] +def GetFieldPop : AccessOpcode; +// [] -> [Value] +def GetThisField : AccessOpcode; + +// [Pointer, Value] -> [Pointer] +def SetField : AccessOpcode; +// [Value] -> [] +def SetThisField : AccessOpcode; + +// [Value] -> [] +def InitThisField : AccessOpcode; +// [Value] -> [] +def InitThisFieldActive : AccessOpcode; +// [Value] -> [] +def InitThisBitField : BitFieldOpcode; +// [Pointer, Value] -> [] +def InitField : AccessOpcode; +// [Pointer, Value] -> [] +def InitBitField : BitFieldOpcode; +// [Pointer, Value] -> [] +def InitFieldActive : AccessOpcode; + +//===----------------------------------------------------------------------===// +// Pointer access +//===----------------------------------------------------------------------===// + +class LoadOpcode : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +// [Pointer] -> [Pointer, Value] +def Load : LoadOpcode {} +// [Pointer] -> [Value] +def LoadPop : LoadOpcode {} + +class StoreOpcode : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +class StoreBitFieldOpcode : Opcode { + let Types = [AluTypeClass]; + let HasGroup = 1; +} + +// [Pointer, Value] -> [Pointer] +def Store : StoreOpcode {} +// [Pointer, Value] -> [] +def StorePop : StoreOpcode {} + +// [Pointer, Value] -> [Pointer] +def StoreBitField : StoreBitFieldOpcode {} +// [Pointer, Value] -> [] +def StoreBitFieldPop : StoreBitFieldOpcode {} + +// [Pointer, Value] -> [] +def InitPop : StoreOpcode {} +// [Pointer, Value] -> [Pointer] +def InitElem : Opcode { + let Types = [AllTypeClass]; + let Args = [ArgUint32]; + let HasGroup = 1; +} +// [Pointer, Value] -> [] +def InitElemPop : Opcode { + let Types = [AllTypeClass]; + let Args = [ArgUint32]; + let HasGroup = 1; +} + +//===----------------------------------------------------------------------===// +// Pointer arithmetic. +//===----------------------------------------------------------------------===// + +// [Pointer, Integral] -> [Pointer] +def AddOffset : AluOpcode; +// [Pointer, Integral] -> [Pointer] +def SubOffset : AluOpcode; + +//===----------------------------------------------------------------------===// +// Binary operators. +//===----------------------------------------------------------------------===// + +// [Real, Real] -> [Real] +def Sub : AluOpcode; +def Add : AluOpcode; +def Mul : AluOpcode; + +//===----------------------------------------------------------------------===// +// Comparison opcodes. +//===----------------------------------------------------------------------===// + +class EqualityOpcode : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +def EQ : EqualityOpcode; +def NE : EqualityOpcode; + +class ComparisonOpcode : Opcode { + let Types = [ComparableTypeClass]; + let HasGroup = 1; +} + +def LT : ComparisonOpcode; +def LE : ComparisonOpcode; +def GT : ComparisonOpcode; +def GE : ComparisonOpcode; + +//===----------------------------------------------------------------------===// +// Stack management. +//===----------------------------------------------------------------------===// + +// [Value] -> [] +def Pop : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} + +// [Value] -> [Value, Value] +def Dup : Opcode { + let Types = [AllTypeClass]; + let HasGroup = 1; +} diff --git a/clang/lib/AST/Interp/Pointer.cpp b/clang/lib/AST/Interp/Pointer.cpp new file mode 100644 index 000000000000..1a10723aaca5 --- /dev/null +++ b/clang/lib/AST/Interp/Pointer.cpp @@ -0,0 +1,193 @@ +//===--- Pointer.cpp - Types for the constexpr VM ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Pointer.h" +#include "Block.h" +#include "Function.h" +#include "PrimType.h" + +using namespace clang; +using namespace clang::interp; + +Pointer::Pointer(Block *Pointee) : Pointer(Pointee, 0, 0) {} + +Pointer::Pointer(const Pointer &P) : Pointer(P.Pointee, P.Base, P.Offset) {} + +Pointer::Pointer(Pointer &&P) + : Pointee(P.Pointee), Base(P.Base), Offset(P.Offset) { + if (Pointee) + Pointee->movePointer(&P, this); +} + +Pointer::Pointer(Block *Pointee, unsigned Base, unsigned Offset) + : Pointee(Pointee), Base(Base), Offset(Offset) { + assert((Base == RootPtrMark || Base % alignof(void *) == 0) && "wrong base"); + if (Pointee) + Pointee->addPointer(this); +} + +Pointer::~Pointer() { + if (Pointee) { + Pointee->removePointer(this); + Pointee->cleanup(); + } +} + +void Pointer::operator=(const Pointer &P) { + Block *Old = Pointee; + + if (Pointee) + Pointee->removePointer(this); + + Offset = P.Offset; + Base = P.Base; + + Pointee = P.Pointee; + if (Pointee) + Pointee->addPointer(this); + + if (Old) + Old->cleanup(); +} + +void Pointer::operator=(Pointer &&P) { + Block *Old = Pointee; + + if (Pointee) + Pointee->removePointer(this); + + Offset = P.Offset; + Base = P.Base; + + Pointee = P.Pointee; + if (Pointee) + Pointee->movePointer(&P, this); + + if (Old) + Old->cleanup(); +} + +APValue Pointer::toAPValue() const { + APValue::LValueBase Base; + llvm::SmallVector<APValue::LValuePathEntry, 5> Path; + CharUnits Offset; + bool IsNullPtr; + bool IsOnePastEnd; + + if (isZero()) { + Base = static_cast<const Expr *>(nullptr); + IsNullPtr = true; + IsOnePastEnd = false; + Offset = CharUnits::Zero(); + } else { + // Build the lvalue base from the block. + Descriptor *Desc = getDeclDesc(); + if (auto *VD = Desc->asValueDecl()) + Base = VD; + else if (auto *E = Desc->asExpr()) + Base = E; + else + llvm_unreachable("Invalid allocation type"); + + // Not a null pointer. + IsNullPtr = false; + + if (isUnknownSizeArray()) { + IsOnePastEnd = false; + Offset = CharUnits::Zero(); + } else { + // TODO: compute the offset into the object. + Offset = CharUnits::Zero(); + + // Build the path into the object. + Pointer Ptr = *this; + while (Ptr.isField()) { + if (Ptr.isArrayElement()) { + Path.push_back(APValue::LValuePathEntry::ArrayIndex(Ptr.getIndex())); + Ptr = Ptr.getArray(); + } else { + // TODO: figure out if base is virtual + bool IsVirtual = false; + + // Create a path entry for the field. + Descriptor *Desc = Ptr.getFieldDesc(); + if (auto *BaseOrMember = Desc->asDecl()) { + Path.push_back(APValue::LValuePathEntry({BaseOrMember, IsVirtual})); + Ptr = Ptr.getBase(); + continue; + } + llvm_unreachable("Invalid field type"); + } + } + + IsOnePastEnd = isOnePastEnd(); + } + } + + return APValue(Base, Offset, Path, IsOnePastEnd, IsNullPtr); +} + +bool Pointer::isInitialized() const { + assert(Pointee && "Cannot check if null pointer was initialized"); + Descriptor *Desc = getFieldDesc(); + if (Desc->isPrimitiveArray()) { + if (Pointee->IsStatic) + return true; + // Primitive array field are stored in a bitset. + InitMap *Map = getInitMap(); + if (!Map) + return false; + if (Map == (InitMap *)-1) + return true; + return Map->isInitialized(getIndex()); + } else { + // Field has its bit in an inline descriptor. + return Base == 0 || getInlineDesc()->IsInitialized; + } +} + +void Pointer::initialize() const { + assert(Pointee && "Cannot initialize null pointer"); + Descriptor *Desc = getFieldDesc(); + if (Desc->isPrimitiveArray()) { + if (!Pointee->IsStatic) { + // Primitive array initializer. + InitMap *&Map = getInitMap(); + if (Map == (InitMap *)-1) + return; + if (Map == nullptr) + Map = InitMap::allocate(Desc->getNumElems()); + if (Map->initialize(getIndex())) { + free(Map); + Map = (InitMap *)-1; + } + } + } else { + // Field has its bit in an inline descriptor. + assert(Base != 0 && "Only composite fields can be initialised"); + getInlineDesc()->IsInitialized = true; + } +} + +void Pointer::activate() const { + // Field has its bit in an inline descriptor. + assert(Base != 0 && "Only composite fields can be initialised"); + getInlineDesc()->IsActive = true; +} + +void Pointer::deactivate() const { + // TODO: this only appears in constructors, so nothing to deactivate. +} + +bool Pointer::hasSameBase(const Pointer &A, const Pointer &B) { + return A.Pointee == B.Pointee; +} + +bool Pointer::hasSameArray(const Pointer &A, const Pointer &B) { + return A.Base == B.Base && A.getFieldDesc()->IsArray; +} diff --git a/clang/lib/AST/Interp/Pointer.h b/clang/lib/AST/Interp/Pointer.h new file mode 100644 index 000000000000..b8fa98e24faa --- /dev/null +++ b/clang/lib/AST/Interp/Pointer.h @@ -0,0 +1,353 @@ +//===--- Pointer.h - Types for the constexpr VM -----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the classes responsible for pointer tracking. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_POINTER_H +#define LLVM_CLANG_AST_INTERP_POINTER_H + +#include "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 pointer to a memory block, live or dead. +/// +/// This object can be allocated into interpreter stack frames. If pointing to +/// a live block, it is a link in the chain of pointers pointing to the block. +class Pointer { +private: + static constexpr unsigned PastEndMark = (unsigned)-1; + static constexpr unsigned RootPtrMark = (unsigned)-1; + +public: + Pointer() {} + Pointer(Block *B); + Pointer(const Pointer &P); + Pointer(Pointer &&P); + ~Pointer(); + + void operator=(const Pointer &P); + void operator=(Pointer &&P); + + /// Converts the pointer to an APValue. + APValue toAPValue() const; + + /// Offsets a pointer inside an array. + Pointer atIndex(unsigned Idx) const { + if (Base == RootPtrMark) + return Pointer(Pointee, RootPtrMark, getDeclDesc()->getSize()); + unsigned Off = Idx * elemSize(); + if (getFieldDesc()->ElemDesc) + Off += sizeof(InlineDescriptor); + else + Off += sizeof(InitMap *); + return Pointer(Pointee, Base, Base + Off); + } + + /// Creates a pointer to a field. + Pointer atField(unsigned Off) const { + unsigned Field = Offset + Off; + return Pointer(Pointee, Field, Field); + } + + /// Restricts the scope of an array element pointer. + Pointer narrow() const { + // Null pointers cannot be narrowed. + if (isZero() || isUnknownSizeArray()) + return *this; + + // Pointer to an array of base types - enter block. + if (Base == RootPtrMark) + return Pointer(Pointee, 0, Offset == 0 ? Offset : PastEndMark); + + // Pointer is one past end - magic offset marks that. + if (isOnePastEnd()) + return Pointer(Pointee, Base, PastEndMark); + + // Primitive arrays are a bit special since they do not have inline + // descriptors. If Offset != Base, then the pointer already points to + // an element and there is nothing to do. Otherwise, the pointer is + // adjusted to the first element of the array. + if (inPrimitiveArray()) { + if (Offset != Base) + return *this; + return Pointer(Pointee, Base, Offset + sizeof(InitMap *)); + } + + // Pointer is to a field or array element - enter it. + if (Offset != Base) + return Pointer(Pointee, Offset, Offset); + + // Enter the first element of an array. + if (!getFieldDesc()->isArray()) + return *this; + + const unsigned NewBase = Base + sizeof(InlineDescriptor); + return Pointer(Pointee, NewBase, NewBase); + } + + /// Expands a pointer to the containing array, undoing narrowing. + Pointer expand() const { + if (isElementPastEnd()) { + // Revert to an outer one-past-end pointer. + unsigned Adjust; + if (inPrimitiveArray()) + Adjust = sizeof(InitMap *); + else + Adjust = sizeof(InlineDescriptor); + return Pointer(Pointee, Base, Base + getSize() + Adjust); + } + + // Do not step out of array elements. + if (Base != Offset) + return *this; + + // If at base, point to an array of base types. + if (Base == 0) + return Pointer(Pointee, RootPtrMark, 0); + + // Step into the containing array, if inside one. + unsigned Next = Base - getInlineDesc()->Offset; + Descriptor *Desc = Next == 0 ? getDeclDesc() : getDescriptor(Next)->Desc; + if (!Desc->IsArray) + return *this; + return Pointer(Pointee, Next, Offset); + } + + /// Checks if the pointer is null. + bool isZero() const { return Pointee == nullptr; } + /// Checks if the pointer is live. + bool isLive() const { return Pointee && !Pointee->IsDead; } + /// Checks if the item is a field in an object. + bool isField() const { return Base != 0 && Base != RootPtrMark; } + + /// Accessor for information about the declaration site. + Descriptor *getDeclDesc() const { return Pointee->Desc; } + SourceLocation getDeclLoc() const { return getDeclDesc()->getLocation(); } + + /// Returns a pointer to the object of which this pointer is a field. + Pointer getBase() const { + if (Base == RootPtrMark) { + assert(Offset == PastEndMark && "cannot get base of a block"); + return Pointer(Pointee, Base, 0); + } + assert(Offset == Base && "not an inner field"); + unsigned NewBase = Base - getInlineDesc()->Offset; + return Pointer(Pointee, NewBase, NewBase); + } + /// Returns the parent array. + Pointer getArray() const { + if (Base == RootPtrMark) { + assert(Offset != 0 && Offset != PastEndMark && "not an array element"); + return Pointer(Pointee, Base, 0); + } + assert(Offset != Base && "not an array element"); + return Pointer(Pointee, Base, Base); + } + + /// Accessors for information about the innermost field. + Descriptor *getFieldDesc() const { + if (Base == 0 || Base == RootPtrMark) + return getDeclDesc(); + return getInlineDesc()->Desc; + } + + /// Returns the type of the innermost field. + QualType getType() const { return getFieldDesc()->getType(); } + + /// Returns the element size of the innermost field. + size_t elemSize() const { + if (Base == RootPtrMark) + return getDeclDesc()->getSize(); + return getFieldDesc()->getElemSize(); + } + /// Returns the total size of the innermost field. + size_t getSize() const { return getFieldDesc()->getSize(); } + + /// Returns the offset into an array. + unsigned getOffset() const { + assert(Offset != PastEndMark && "invalid offset"); + if (Base == RootPtrMark) + return Offset; + + unsigned Adjust = 0; + if (Offset != Base) { + if (getFieldDesc()->ElemDesc) + Adjust = sizeof(InlineDescriptor); + else + Adjust = sizeof(InitMap *); + } + return Offset - Base - Adjust; + } + + /// Checks if the innermost field is an array. + bool inArray() const { return getFieldDesc()->IsArray; } + /// Checks if the structure is a primitive array. + bool inPrimitiveArray() const { return getFieldDesc()->isPrimitiveArray(); } + /// Checks if the structure is an array of unknown size. + bool isUnknownSizeArray() const { + return getFieldDesc()->isUnknownSizeArray(); + } + /// Checks if the pointer points to an array. + bool isArrayElement() const { return Base != Offset; } + /// Pointer points directly to a block. + bool isRoot() const { + return (Base == 0 || Base == RootPtrMark) && Offset == 0; + } + + /// Returns the record descriptor of a class. + Record *getRecord() const { return getFieldDesc()->ElemRecord; } + /// Returns the field information. + const FieldDecl *getField() const { return getFieldDesc()->asFieldDecl(); } + + /// Checks if the object is a union. + bool isUnion() const; + + /// Checks if the storage is extern. + bool isExtern() const { return Pointee->isExtern(); } + /// Checks if the storage is static. + bool isStatic() const { return Pointee->isStatic(); } + /// Checks if the storage is temporary. + bool isTemporary() const { return Pointee->isTemporary(); } + /// Checks if the storage is a static temporary. + bool isStaticTemporary() const { return isStatic() && isTemporary(); } + + /// Checks if the field is mutable. + bool isMutable() const { return Base != 0 && getInlineDesc()->IsMutable; } + /// Checks if an object was initialized. + bool isInitialized() const; + /// Checks if the object is active. + bool isActive() const { return Base == 0 || getInlineDesc()->IsActive; } + /// Checks if a structure is a base class. + bool isBaseClass() const { return isField() && getInlineDesc()->IsBase; } + + /// Checks if an object or a subfield is mutable. + bool isConst() const { + return Base == 0 ? getDeclDesc()->IsConst : getInlineDesc()->IsConst; + } + + /// Returns the declaration ID. + llvm::Optional<unsigned> getDeclID() const { return Pointee->getDeclID(); } + + /// Returns the byte offset from the start. + unsigned getByteOffset() const { + return Offset; + } + + /// Returns the number of elements. + unsigned getNumElems() const { return getSize() / elemSize(); } + + /// Returns the index into an array. + int64_t getIndex() const { + if (isElementPastEnd()) + return 1; + if (auto ElemSize = elemSize()) + return getOffset() / ElemSize; + return 0; + } + + /// Checks if the index is one past end. + bool isOnePastEnd() const { + return isElementPastEnd() || getSize() == getOffset(); + } + + /// Checks if the pointer is an out-of-bounds element pointer. + bool isElementPastEnd() const { return Offset == PastEndMark; } + + /// Dereferences the pointer, if it's live. + template <typename T> T &deref() const { + assert(isLive() && "Invalid pointer"); + return *reinterpret_cast<T *>(Pointee->data() + Offset); + } + + /// Dereferences a primitive element. + template <typename T> T &elem(unsigned I) const { + return reinterpret_cast<T *>(Pointee->data())[I]; + } + + /// Initializes a field. + void initialize() const; + /// Activats a field. + void activate() const; + /// Deactivates an entire strurcutre. + void deactivate() const; + + /// Checks if two pointers are comparable. + static bool hasSameBase(const Pointer &A, const Pointer &B); + /// Checks if two pointers can be subtracted. + static bool hasSameArray(const Pointer &A, const Pointer &B); + + /// Prints the pointer. + void print(llvm::raw_ostream &OS) const { + OS << "{" << Base << ", " << Offset << ", "; + if (Pointee) + OS << Pointee->getSize(); + else + OS << "nullptr"; + OS << "}"; + } + +private: + friend class Block; + friend class DeadBlock; + + Pointer(Block *Pointee, unsigned Base, unsigned Offset); + + /// Returns the embedded descriptor preceding a field. + InlineDescriptor *getInlineDesc() const { return getDescriptor(Base); } + + /// Returns a descriptor at a given offset. + InlineDescriptor *getDescriptor(unsigned Offset) const { + assert(Offset != 0 && "Not a nested pointer"); + return reinterpret_cast<InlineDescriptor *>(Pointee->data() + Offset) - 1; + } + + /// Returns a reference to the pointer which stores the initialization map. + InitMap *&getInitMap() const { + return *reinterpret_cast<InitMap **>(Pointee->data() + Base); + } + + /// The block the pointer is pointing to. + Block *Pointee = nullptr; + /// Start of the current subfield. + unsigned Base = 0; + /// Offset into the block. + unsigned Offset = 0; + + /// Previous link in the pointer chain. + Pointer *Prev = nullptr; + /// Next link in the pointer chain. + Pointer *Next = nullptr; +}; + +inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Pointer &P) { + P.print(OS); + return OS; +} + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/PrimType.cpp b/clang/lib/AST/Interp/PrimType.cpp new file mode 100644 index 000000000000..082bfaf3c207 --- /dev/null +++ b/clang/lib/AST/Interp/PrimType.cpp @@ -0,0 +1,23 @@ +//===--- Type.cpp - Types for the constexpr VM ------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "PrimType.h" + +using namespace clang; +using namespace clang::interp; + +namespace clang { +namespace interp { + +size_t primSize(PrimType Type) { + TYPE_SWITCH(Type, return sizeof(T)); + llvm_unreachable("not a primitive type"); +} + +} // namespace interp +} // namespace clang diff --git a/clang/lib/AST/Interp/PrimType.h b/clang/lib/AST/Interp/PrimType.h new file mode 100644 index 000000000000..f5f4f8e5c32d --- /dev/null +++ b/clang/lib/AST/Interp/PrimType.h @@ -0,0 +1,115 @@ +//===--- PrimType.h - Types for the constexpr VM --------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the VM types and helpers operating on types. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_TYPE_H +#define LLVM_CLANG_AST_INTERP_TYPE_H + +#include <climits> +#include <cstddef> +#include <cstdint> +#include "Boolean.h" +#include "Integral.h" +#include "Pointer.h" + +namespace clang { +namespace interp { + +/// Enumeration of the primitive types of the VM. +enum PrimType : unsigned { + PT_Sint8, + PT_Uint8, + PT_Sint16, + PT_Uint16, + PT_Sint32, + PT_Uint32, + PT_Sint64, + PT_Uint64, + PT_Bool, + PT_Ptr, +}; + +/// Mapping from primitive types to their representation. +template <PrimType T> struct PrimConv; +template <> struct PrimConv<PT_Sint8> { using T = Integral<8, true>; }; +template <> struct PrimConv<PT_Uint8> { using T = Integral<8, false>; }; +template <> struct PrimConv<PT_Sint16> { using T = Integral<16, true>; }; +template <> struct PrimConv<PT_Uint16> { using T = Integral<16, false>; }; +template <> struct PrimConv<PT_Sint32> { using T = Integral<32, true>; }; +template <> struct PrimConv<PT_Uint32> { using T = Integral<32, false>; }; +template <> struct PrimConv<PT_Sint64> { using T = Integral<64, true>; }; +template <> struct PrimConv<PT_Uint64> { using T = Integral<64, false>; }; +template <> struct PrimConv<PT_Bool> { using T = Boolean; }; +template <> struct PrimConv<PT_Ptr> { using T = Pointer; }; + +/// Returns the size of a primitive type in bytes. +size_t primSize(PrimType Type); + +/// Aligns a size to the pointer alignment. +constexpr size_t align(size_t Size) { + return ((Size + alignof(void *) - 1) / alignof(void *)) * alignof(void *); +} + +inline bool isPrimitiveIntegral(PrimType Type) { + switch (Type) { + case PT_Bool: + case PT_Sint8: + case PT_Uint8: + case PT_Sint16: + case PT_Uint16: + case PT_Sint32: + case PT_Uint32: + case PT_Sint64: + case PT_Uint64: + return true; + default: + return false; + } +} + +} // namespace interp +} // namespace clang + +/// Helper macro to simplify type switches. +/// The macro implicitly exposes a type T in the scope of the inner block. +#define TYPE_SWITCH_CASE(Name, B) \ + case Name: { using T = PrimConv<Name>::T; do {B;} while(0); break; } +#define TYPE_SWITCH(Expr, B) \ + switch (Expr) { \ + TYPE_SWITCH_CASE(PT_Sint8, B) \ + TYPE_SWITCH_CASE(PT_Uint8, B) \ + TYPE_SWITCH_CASE(PT_Sint16, B) \ + TYPE_SWITCH_CASE(PT_Uint16, B) \ + TYPE_SWITCH_CASE(PT_Sint32, B) \ + TYPE_SWITCH_CASE(PT_Uint32, B) \ + TYPE_SWITCH_CASE(PT_Sint64, B) \ + TYPE_SWITCH_CASE(PT_Uint64, B) \ + TYPE_SWITCH_CASE(PT_Bool, B) \ + TYPE_SWITCH_CASE(PT_Ptr, B) \ + } +#define COMPOSITE_TYPE_SWITCH(Expr, B, D) \ + switch (Expr) { \ + TYPE_SWITCH_CASE(PT_Ptr, B) \ + default: do { D; } while(0); break; \ + } +#define INT_TYPE_SWITCH(Expr, B) \ + switch (Expr) { \ + TYPE_SWITCH_CASE(PT_Sint8, B) \ + TYPE_SWITCH_CASE(PT_Uint8, B) \ + TYPE_SWITCH_CASE(PT_Sint16, B) \ + TYPE_SWITCH_CASE(PT_Uint16, B) \ + TYPE_SWITCH_CASE(PT_Sint32, B) \ + TYPE_SWITCH_CASE(PT_Uint32, B) \ + TYPE_SWITCH_CASE(PT_Sint64, B) \ + TYPE_SWITCH_CASE(PT_Uint64, B) \ + default: llvm_unreachable("not an integer"); \ + } +#endif diff --git a/clang/lib/AST/Interp/Program.cpp b/clang/lib/AST/Interp/Program.cpp new file mode 100644 index 000000000000..fcbab0ea8172 --- /dev/null +++ b/clang/lib/AST/Interp/Program.cpp @@ -0,0 +1,364 @@ +//===--- Program.cpp - Bytecode for the constexpr VM ------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Program.h" +#include "ByteCodeStmtGen.h" +#include "Context.h" +#include "Function.h" +#include "Opcode.h" +#include "PrimType.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclCXX.h" + +using namespace clang; +using namespace clang::interp; + +unsigned Program::createGlobalString(const StringLiteral *S) { + const size_t CharWidth = S->getCharByteWidth(); + const size_t BitWidth = CharWidth * Ctx.getCharBit(); + + PrimType CharType; + switch (CharWidth) { + case 1: + CharType = PT_Sint8; + break; + case 2: + CharType = PT_Uint16; + break; + case 4: + CharType = PT_Uint32; + break; + default: + llvm_unreachable("unsupported character width"); + } + + // Create a descriptor for the string. + Descriptor *Desc = allocateDescriptor(S, CharType, S->getLength() + 1, + /*isConst=*/true, + /*isTemporary=*/false, + /*isMutable=*/false); + + // Allocate storage for the string. + // The byte length does not include the null terminator. + unsigned I = Globals.size(); + unsigned Sz = Desc->getAllocSize(); + auto *G = new (Allocator, Sz) Global(Desc, /*isStatic=*/true, + /*isExtern=*/false); + Globals.push_back(G); + + // Construct the string in storage. + const Pointer Ptr(G->block()); + for (unsigned I = 0, N = S->getLength(); I <= N; ++I) { + Pointer Field = Ptr.atIndex(I).narrow(); + const uint32_t CodePoint = I == N ? 0 : S->getCodeUnit(I); + switch (CharType) { + case PT_Sint8: { + using T = PrimConv<PT_Sint8>::T; + Field.deref<T>() = T::from(CodePoint, BitWidth); + break; + } + case PT_Uint16: { + using T = PrimConv<PT_Uint16>::T; + Field.deref<T>() = T::from(CodePoint, BitWidth); + break; + } + case PT_Uint32: { + using T = PrimConv<PT_Uint32>::T; + Field.deref<T>() = T::from(CodePoint, BitWidth); + break; + } + default: + llvm_unreachable("unsupported character type"); + } + } + return I; +} + +Pointer Program::getPtrGlobal(unsigned Idx) { + assert(Idx < Globals.size()); + return Pointer(Globals[Idx]->block()); +} + +llvm::Optional<unsigned> Program::getGlobal(const ValueDecl *VD) { + auto It = GlobalIndices.find(VD); + if (It != GlobalIndices.end()) + return It->second; + + // Find any previous declarations which were aleady evaluated. + llvm::Optional<unsigned> Index; + for (const Decl *P = VD; P; P = P->getPreviousDecl()) { + auto It = GlobalIndices.find(P); + if (It != GlobalIndices.end()) { + Index = It->second; + break; + } + } + + // Map the decl to the existing index. + if (Index) { + GlobalIndices[VD] = *Index; + return {}; + } + + return Index; +} + +llvm::Optional<unsigned> Program::getOrCreateGlobal(const ValueDecl *VD) { + if (auto Idx = getGlobal(VD)) + return Idx; + + if (auto Idx = createGlobal(VD)) { + GlobalIndices[VD] = *Idx; + return Idx; + } + return {}; +} + +llvm::Optional<unsigned> Program::getOrCreateDummy(const ParmVarDecl *PD) { + auto &ASTCtx = Ctx.getASTContext(); + + // Create a pointer to an incomplete array of the specified elements. + QualType ElemTy = PD->getType()->castAs<PointerType>()->getPointeeType(); + QualType Ty = ASTCtx.getIncompleteArrayType(ElemTy, ArrayType::Normal, 0); + + // Dedup blocks since they are immutable and pointers cannot be compared. + auto It = DummyParams.find(PD); + if (It != DummyParams.end()) + return It->second; + + if (auto Idx = createGlobal(PD, Ty, /*isStatic=*/true, /*isExtern=*/true)) { + DummyParams[PD] = *Idx; + return Idx; + } + return {}; +} + +llvm::Optional<unsigned> Program::createGlobal(const ValueDecl *VD) { + bool IsStatic, IsExtern; + if (auto *Var = dyn_cast<VarDecl>(VD)) { + IsStatic = !Var->hasLocalStorage(); + IsExtern = !Var->getAnyInitializer(); + } else { + IsStatic = false; + IsExtern = true; + } + if (auto Idx = createGlobal(VD, VD->getType(), IsStatic, IsExtern)) { + for (const Decl *P = VD; P; P = P->getPreviousDecl()) + GlobalIndices[P] = *Idx; + return *Idx; + } + return {}; +} + +llvm::Optional<unsigned> Program::createGlobal(const Expr *E) { + return createGlobal(E, E->getType(), /*isStatic=*/true, /*isExtern=*/false); +} + +llvm::Optional<unsigned> Program::createGlobal(const DeclTy &D, QualType Ty, + bool IsStatic, bool IsExtern) { + // Create a descriptor for the global. + Descriptor *Desc; + const bool IsConst = Ty.isConstQualified(); + const bool IsTemporary = D.dyn_cast<const Expr *>(); + if (auto T = Ctx.classify(Ty)) { + Desc = createDescriptor(D, *T, IsConst, IsTemporary); + } else { + Desc = createDescriptor(D, Ty.getTypePtr(), IsConst, IsTemporary); + } + if (!Desc) + return {}; + + // Allocate a block for storage. + unsigned I = Globals.size(); + + auto *G = new (Allocator, Desc->getAllocSize()) + Global(getCurrentDecl(), Desc, IsStatic, IsExtern); + G->block()->invokeCtor(); + + Globals.push_back(G); + + return I; +} + +Function *Program::getFunction(const FunctionDecl *F) { + F = F->getDefinition(); + auto It = Funcs.find(F); + return It == Funcs.end() ? nullptr : It->second.get(); +} + +llvm::Expected<Function *> Program::getOrCreateFunction(const FunctionDecl *F) { + if (Function *Func = getFunction(F)) { + return Func; + } + + // Try to compile the function if it wasn't compiled yet. + if (const FunctionDecl *FD = F->getDefinition()) + return ByteCodeStmtGen<ByteCodeEmitter>(Ctx, *this).compileFunc(FD); + + // A relocation which traps if not resolved. + return nullptr; +} + +Record *Program::getOrCreateRecord(const RecordDecl *RD) { + // Use the actual definition as a key. + RD = RD->getDefinition(); + if (!RD) + return nullptr; + + // Deduplicate records. + auto It = Records.find(RD); + if (It != Records.end()) { + return It->second; + } + + // Number of bytes required by fields and base classes. + unsigned Size = 0; + // Number of bytes required by virtual base. + unsigned VirtSize = 0; + + // Helper to get a base descriptor. + auto GetBaseDesc = [this](const RecordDecl *BD, Record *BR) -> Descriptor * { + if (!BR) + return nullptr; + return allocateDescriptor(BD, BR, /*isConst=*/false, + /*isTemporary=*/false, + /*isMutable=*/false); + }; + + // Reserve space for base classes. + Record::BaseList Bases; + Record::VirtualBaseList VirtBases; + if (auto *CD = dyn_cast<CXXRecordDecl>(RD)) { + for (const CXXBaseSpecifier &Spec : CD->bases()) { + if (Spec.isVirtual()) + continue; + + const RecordDecl *BD = Spec.getType()->castAs<RecordType>()->getDecl(); + Record *BR = getOrCreateRecord(BD); + if (Descriptor *Desc = GetBaseDesc(BD, BR)) { + Size += align(sizeof(InlineDescriptor)); + Bases.push_back({BD, Size, Desc, BR}); + Size += align(BR->getSize()); + continue; + } + return nullptr; + } + + for (const CXXBaseSpecifier &Spec : CD->vbases()) { + const RecordDecl *BD = Spec.getType()->castAs<RecordType>()->getDecl(); + Record *BR = getOrCreateRecord(BD); + + if (Descriptor *Desc = GetBaseDesc(BD, BR)) { + VirtSize += align(sizeof(InlineDescriptor)); + VirtBases.push_back({BD, VirtSize, Desc, BR}); + VirtSize += align(BR->getSize()); + continue; + } + return nullptr; + } + } + + // Reserve space for fields. + Record::FieldList Fields; + for (const FieldDecl *FD : RD->fields()) { + // Reserve space for the field's descriptor and the offset. + Size += align(sizeof(InlineDescriptor)); + + // Classify the field and add its metadata. + QualType FT = FD->getType(); + const bool IsConst = FT.isConstQualified(); + const bool IsMutable = FD->isMutable(); + Descriptor *Desc; + if (llvm::Optional<PrimType> T = Ctx.classify(FT)) { + Desc = createDescriptor(FD, *T, IsConst, /*isTemporary=*/false, + IsMutable); + } else { + Desc = createDescriptor(FD, FT.getTypePtr(), IsConst, + /*isTemporary=*/false, IsMutable); + } + if (!Desc) + return nullptr; + Fields.push_back({FD, Size, Desc}); + Size += align(Desc->getAllocSize()); + } + + Record *R = new (Allocator) Record(RD, std::move(Bases), std::move(Fields), + std::move(VirtBases), VirtSize, Size); + Records.insert({RD, R}); + return R; +} + +Descriptor *Program::createDescriptor(const DeclTy &D, const Type *Ty, + bool IsConst, bool IsTemporary, + bool IsMutable) { + // Classes and structures. + if (auto *RT = Ty->getAs<RecordType>()) { + if (auto *Record = getOrCreateRecord(RT->getDecl())) + return allocateDescriptor(D, Record, IsConst, IsTemporary, IsMutable); + } + + // Arrays. + if (auto ArrayType = Ty->getAsArrayTypeUnsafe()) { + QualType ElemTy = ArrayType->getElementType(); + // Array of well-known bounds. + if (auto CAT = dyn_cast<ConstantArrayType>(ArrayType)) { + size_t NumElems = CAT->getSize().getZExtValue(); + if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) { + // Arrays of primitives. + unsigned ElemSize = primSize(*T); + if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems) { + return {}; + } + return allocateDescriptor(D, *T, NumElems, IsConst, IsTemporary, + IsMutable); + } else { + // Arrays of composites. In this case, the array is a list of pointers, + // followed by the actual elements. + Descriptor *Desc = + createDescriptor(D, ElemTy.getTypePtr(), IsConst, IsTemporary); + if (!Desc) + return nullptr; + InterpSize ElemSize = Desc->getAllocSize() + sizeof(InlineDescriptor); + if (std::numeric_limits<unsigned>::max() / ElemSize <= NumElems) + return {}; + return allocateDescriptor(D, Desc, NumElems, IsConst, IsTemporary, + IsMutable); + } + } + + // Array of unknown bounds - cannot be accessed and pointer arithmetic + // is forbidden on pointers to such objects. + if (isa<IncompleteArrayType>(ArrayType)) { + if (llvm::Optional<PrimType> T = Ctx.classify(ElemTy)) { + return allocateDescriptor(D, *T, IsTemporary, + Descriptor::UnknownSize{}); + } else { + Descriptor *Desc = + createDescriptor(D, ElemTy.getTypePtr(), IsConst, IsTemporary); + if (!Desc) + return nullptr; + return allocateDescriptor(D, Desc, IsTemporary, + Descriptor::UnknownSize{}); + } + } + } + + // Atomic types. + if (auto *AT = Ty->getAs<AtomicType>()) { + const Type *InnerTy = AT->getValueType().getTypePtr(); + return createDescriptor(D, InnerTy, IsConst, IsTemporary, IsMutable); + } + + // Complex types - represented as arrays of elements. + if (auto *CT = Ty->getAs<ComplexType>()) { + PrimType ElemTy = *Ctx.classify(CT->getElementType()); + return allocateDescriptor(D, ElemTy, 2, IsConst, IsTemporary, IsMutable); + } + + return nullptr; +} diff --git a/clang/lib/AST/Interp/Program.h b/clang/lib/AST/Interp/Program.h new file mode 100644 index 000000000000..5f0012db9b3f --- /dev/null +++ b/clang/lib/AST/Interp/Program.h @@ -0,0 +1,220 @@ +//===--- Program.h - Bytecode for the constexpr VM --------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines a program which organises and links multiple bytecode functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_PROGRAM_H +#define LLVM_CLANG_AST_INTERP_PROGRAM_H + +#include <map> +#include <vector> +#include "Function.h" +#include "Pointer.h" +#include "PrimType.h" +#include "Record.h" +#include "Source.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerUnion.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Allocator.h" + +namespace clang { +class RecordDecl; +class Expr; +class FunctionDecl; +class Stmt; +class StringLiteral; +class VarDecl; + +namespace interp { +class Context; +class State; +class Record; +class Scope; + +/// The program contains and links the bytecode for all functions. +class Program { +public: + Program(Context &Ctx) : Ctx(Ctx) {} + + /// Emits a string literal among global data. + unsigned createGlobalString(const StringLiteral *S); + + /// Returns a pointer to a global. + Pointer getPtrGlobal(unsigned Idx); + + /// Returns the value of a global. + Block *getGlobal(unsigned Idx) { + assert(Idx < Globals.size()); + return Globals[Idx]->block(); + } + + /// Finds a global's index. + llvm::Optional<unsigned> getGlobal(const ValueDecl *VD); + + /// Returns or creates a global an creates an index to it. + llvm::Optional<unsigned> getOrCreateGlobal(const ValueDecl *VD); + + /// Returns or creates a dummy value for parameters. + llvm::Optional<unsigned> getOrCreateDummy(const ParmVarDecl *PD); + + /// Creates a global and returns its index. + llvm::Optional<unsigned> createGlobal(const ValueDecl *VD); + + /// Creates a global from a lifetime-extended temporary. + llvm::Optional<unsigned> createGlobal(const Expr *E); + + /// Creates a new function from a code range. + template <typename... Ts> + Function *createFunction(const FunctionDecl *Def, Ts &&... Args) { + auto *Func = new Function(*this, Def, std::forward<Ts>(Args)...); + Funcs.insert({Def, std::unique_ptr<Function>(Func)}); + return Func; + } + /// Creates an anonymous function. + template <typename... Ts> + Function *createFunction(Ts &&... Args) { + auto *Func = new Function(*this, std::forward<Ts>(Args)...); + AnonFuncs.emplace_back(Func); + return Func; + } + + /// Returns a function. + Function *getFunction(const FunctionDecl *F); + + /// Returns a pointer to a function if it exists and can be compiled. + /// If a function couldn't be compiled, an error is returned. + /// If a function was not yet defined, a null pointer is returned. + llvm::Expected<Function *> getOrCreateFunction(const FunctionDecl *F); + + /// Returns a record or creates one if it does not exist. + Record *getOrCreateRecord(const RecordDecl *RD); + + /// Creates a descriptor for a primitive type. + Descriptor *createDescriptor(const DeclTy &D, PrimType Type, + bool IsConst = false, + bool IsTemporary = false, + bool IsMutable = false) { + return allocateDescriptor(D, Type, IsConst, IsTemporary, IsMutable); + } + + /// Creates a descriptor for a composite type. + Descriptor *createDescriptor(const DeclTy &D, const Type *Ty, + bool IsConst = false, bool IsTemporary = false, + bool IsMutable = false); + + /// Context to manage declaration lifetimes. + class DeclScope { + public: + DeclScope(Program &P, const VarDecl *VD) : P(P) { P.startDeclaration(VD); } + ~DeclScope() { P.endDeclaration(); } + + private: + Program &P; + }; + + /// Returns the current declaration ID. + llvm::Optional<unsigned> getCurrentDecl() const { + if (CurrentDeclaration == NoDeclaration) + return llvm::Optional<unsigned>{}; + return LastDeclaration; + } + +private: + friend class DeclScope; + + llvm::Optional<unsigned> createGlobal(const DeclTy &D, QualType Ty, + bool IsStatic, bool IsExtern); + + /// Reference to the VM context. + Context &Ctx; + /// Mapping from decls to cached bytecode functions. + llvm::DenseMap<const FunctionDecl *, std::unique_ptr<Function>> Funcs; + /// List of anonymous functions. + std::vector<std::unique_ptr<Function>> AnonFuncs; + + /// Function relocation locations. + llvm::DenseMap<const FunctionDecl *, std::vector<unsigned>> Relocs; + + /// Custom allocator for global storage. + using PoolAllocTy = llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator>; + + /// Descriptor + storage for a global object. + /// + /// Global objects never go out of scope, thus they do not track pointers. + class Global { + public: + /// Create a global descriptor for string literals. + template <typename... Tys> + Global(Tys... Args) : B(std::forward<Tys>(Args)...) {} + + /// Allocates the global in the pool, reserving storate for data. + void *operator new(size_t Meta, PoolAllocTy &Alloc, size_t Data) { + return Alloc.Allocate(Meta + Data, alignof(void *)); + } + + /// Return a pointer to the data. + char *data() { return B.data(); } + /// Return a pointer to the block. + Block *block() { return &B; } + + private: + /// Required metadata - does not actually track pointers. + Block B; + }; + + /// Allocator for globals. + PoolAllocTy Allocator; + + /// Global objects. + std::vector<Global *> Globals; + /// Cached global indices. + llvm::DenseMap<const void *, unsigned> GlobalIndices; + + /// Mapping from decls to record metadata. + llvm::DenseMap<const RecordDecl *, Record *> Records; + + /// Dummy parameter to generate pointers from. + llvm::DenseMap<const ParmVarDecl *, unsigned> DummyParams; + + /// Creates a new descriptor. + template <typename... Ts> + Descriptor *allocateDescriptor(Ts &&... Args) { + return new (Allocator) Descriptor(std::forward<Ts>(Args)...); + } + + /// No declaration ID. + static constexpr unsigned NoDeclaration = (unsigned)-1; + /// Last declaration ID. + unsigned LastDeclaration = 0; + /// Current declaration ID. + unsigned CurrentDeclaration = NoDeclaration; + + /// Starts evaluating a declaration. + void startDeclaration(const VarDecl *Decl) { + LastDeclaration += 1; + CurrentDeclaration = LastDeclaration; + } + + /// Ends a global declaration. + void endDeclaration() { + CurrentDeclaration = NoDeclaration; + } + +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/Record.cpp b/clang/lib/AST/Interp/Record.cpp new file mode 100644 index 000000000000..f440c4705051 --- /dev/null +++ b/clang/lib/AST/Interp/Record.cpp @@ -0,0 +1,46 @@ +//===--- Record.cpp - struct and class metadata 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 "Record.h" + +using namespace clang; +using namespace clang::interp; + +Record::Record(const RecordDecl *Decl, BaseList &&SrcBases, + FieldList &&SrcFields, VirtualBaseList &&SrcVirtualBases, + unsigned VirtualSize, unsigned BaseSize) + : Decl(Decl), Bases(std::move(SrcBases)), Fields(std::move(SrcFields)), + BaseSize(BaseSize), VirtualSize(VirtualSize) { + for (Base &V : SrcVirtualBases) + VirtualBases.push_back({ V.Decl, V.Offset + BaseSize, V.Desc, V.R }); + + for (Base &B : Bases) + BaseMap[B.Decl] = &B; + for (Field &F : Fields) + FieldMap[F.Decl] = &F; + for (Base &V : VirtualBases) + VirtualBaseMap[V.Decl] = &V; +} + +const Record::Field *Record::getField(const FieldDecl *FD) const { + auto It = FieldMap.find(FD); + assert(It != FieldMap.end() && "Missing field"); + return It->second; +} + +const Record::Base *Record::getBase(const RecordDecl *FD) const { + auto It = BaseMap.find(FD); + assert(It != BaseMap.end() && "Missing base"); + return It->second; +} + +const Record::Base *Record::getVirtualBase(const RecordDecl *FD) const { + auto It = VirtualBaseMap.find(FD); + assert(It != VirtualBaseMap.end() && "Missing virtual base"); + return It->second; +} diff --git a/clang/lib/AST/Interp/Record.h b/clang/lib/AST/Interp/Record.h new file mode 100644 index 000000000000..9cdee9003752 --- /dev/null +++ b/clang/lib/AST/Interp/Record.h @@ -0,0 +1,121 @@ +//===--- Record.h - struct and class metadata 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 +// +//===----------------------------------------------------------------------===// +// +// A record is part of a program to describe the layout and methods of a struct. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_RECORD_H +#define LLVM_CLANG_AST_INTERP_RECORD_H + +#include "Pointer.h" + +namespace clang { +namespace interp { +class Program; + +/// Structure/Class descriptor. +class Record { +public: + /// Describes a record field. + struct Field { + const FieldDecl *Decl; + unsigned Offset; + Descriptor *Desc; + }; + + /// Describes a base class. + struct Base { + const RecordDecl *Decl; + unsigned Offset; + Descriptor *Desc; + Record *R; + }; + + /// Mapping from identifiers to field descriptors. + using FieldList = llvm::SmallVector<Field, 8>; + /// Mapping from identifiers to base classes. + using BaseList = llvm::SmallVector<Base, 8>; + /// List of virtual base classes. + using VirtualBaseList = llvm::SmallVector<Base, 2>; + +public: + /// Returns the underlying declaration. + const RecordDecl *getDecl() const { return Decl; } + /// Checks if the record is a union. + bool isUnion() const { return getDecl()->isUnion(); } + /// Returns the size of the record. + unsigned getSize() const { return BaseSize; } + /// Returns the full size of the record, including records. + unsigned getFullSize() const { return BaseSize + VirtualSize; } + /// Returns a field. + const Field *getField(const FieldDecl *FD) const; + /// Returns a base descriptor. + const Base *getBase(const RecordDecl *FD) const; + /// Returns a virtual base descriptor. + const Base *getVirtualBase(const RecordDecl *RD) const; + + using const_field_iter = FieldList::const_iterator; + llvm::iterator_range<const_field_iter> fields() const { + return llvm::make_range(Fields.begin(), Fields.end()); + } + + unsigned getNumFields() { return Fields.size(); } + Field *getField(unsigned I) { return &Fields[I]; } + + using const_base_iter = BaseList::const_iterator; + llvm::iterator_range<const_base_iter> bases() const { + return llvm::make_range(Bases.begin(), Bases.end()); + } + + unsigned getNumBases() { return Bases.size(); } + Base *getBase(unsigned I) { return &Bases[I]; } + + using const_virtual_iter = VirtualBaseList::const_iterator; + llvm::iterator_range<const_virtual_iter> virtual_bases() const { + return llvm::make_range(VirtualBases.begin(), VirtualBases.end()); + } + + unsigned getNumVirtualBases() { return VirtualBases.size(); } + Base *getVirtualBase(unsigned I) { return &VirtualBases[I]; } + +private: + /// Constructor used by Program to create record descriptors. + Record(const RecordDecl *, BaseList &&Bases, FieldList &&Fields, + VirtualBaseList &&VirtualBases, unsigned VirtualSize, + unsigned BaseSize); + +private: + friend class Program; + + /// Original declaration. + const RecordDecl *Decl; + /// List of all base classes. + BaseList Bases; + /// List of all the fields in the record. + FieldList Fields; + /// List o fall virtual bases. + VirtualBaseList VirtualBases; + + /// Mapping from declarations to bases. + llvm::DenseMap<const RecordDecl *, Base *> BaseMap; + /// Mapping from field identifiers to descriptors. + llvm::DenseMap<const FieldDecl *, Field *> FieldMap; + /// Mapping from declarations to virtual bases. + llvm::DenseMap<const RecordDecl *, Base *> VirtualBaseMap; + /// Mapping from + /// Size of the structure. + unsigned BaseSize; + /// Size of all virtual bases. + unsigned VirtualSize; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/Source.cpp b/clang/lib/AST/Interp/Source.cpp new file mode 100644 index 000000000000..4bec87812638 --- /dev/null +++ b/clang/lib/AST/Interp/Source.cpp @@ -0,0 +1,39 @@ +//===--- Source.cpp - Source expression tracking ----------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "Source.h" +#include "clang/AST/Expr.h" + +using namespace clang; +using namespace clang::interp; + +SourceLocation SourceInfo::getLoc() const { + if (const Expr *E = asExpr()) + return E->getExprLoc(); + if (const Stmt *S = asStmt()) + return S->getBeginLoc(); + if (const Decl *D = asDecl()) + return D->getBeginLoc(); + return SourceLocation(); +} + +const Expr *SourceInfo::asExpr() const { + if (auto *S = Source.dyn_cast<const Stmt *>()) + return dyn_cast<Expr>(S); + return nullptr; +} + +const Expr *SourceMapper::getExpr(Function *F, CodePtr PC) const { + if (const Expr *E = getSource(F, PC).asExpr()) + return E; + llvm::report_fatal_error("missing source expression"); +} + +SourceLocation SourceMapper::getLocation(Function *F, CodePtr PC) const { + return getSource(F, PC).getLoc(); +} diff --git a/clang/lib/AST/Interp/Source.h b/clang/lib/AST/Interp/Source.h new file mode 100644 index 000000000000..e591c3399d7c --- /dev/null +++ b/clang/lib/AST/Interp/Source.h @@ -0,0 +1,118 @@ +//===--- Source.h - Source location provider for the VM --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines a program which organises and links multiple bytecode functions. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_SOURCE_H +#define LLVM_CLANG_AST_INTERP_SOURCE_H + +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "llvm/Support/Endian.h" + +namespace clang { +namespace interp { +class Function; + +/// Pointer into the code segment. +class CodePtr { +public: + CodePtr() : Ptr(nullptr) {} + + CodePtr &operator+=(int32_t Offset) { + Ptr += Offset; + return *this; + } + + int32_t operator-(const CodePtr &RHS) const { + assert(Ptr != nullptr && RHS.Ptr != nullptr && "Invalid code pointer"); + return Ptr - RHS.Ptr; + } + + CodePtr operator-(size_t RHS) const { + assert(Ptr != nullptr && "Invalid code pointer"); + return CodePtr(Ptr - RHS); + } + + bool operator!=(const CodePtr &RHS) const { return Ptr != RHS.Ptr; } + + /// Reads data and advances the pointer. + template <typename T> T read() { + T Value = ReadHelper<T>(Ptr); + Ptr += sizeof(T); + return Value; + } + +private: + /// Constructor used by Function to generate pointers. + CodePtr(const char *Ptr) : Ptr(Ptr) {} + + /// Helper to decode a value or a pointer. + template <typename T> + static typename std::enable_if<!std::is_pointer<T>::value, T>::type + ReadHelper(const char *Ptr) { + using namespace llvm::support; + return endian::read<T, endianness::native, 1>(Ptr); + } + + template <typename T> + static typename std::enable_if<std::is_pointer<T>::value, T>::type + ReadHelper(const char *Ptr) { + using namespace llvm::support; + auto Punned = endian::read<uintptr_t, endianness::native, 1>(Ptr); + return reinterpret_cast<T>(Punned); + } + +private: + friend class Function; + + /// Pointer into the code owned by a function. + const char *Ptr; +}; + +/// Describes the statement/declaration an opcode was generated from. +class SourceInfo { +public: + SourceInfo() {} + SourceInfo(const Stmt *E) : Source(E) {} + SourceInfo(const Decl *D) : Source(D) {} + + SourceLocation getLoc() const; + + const Stmt *asStmt() const { return Source.dyn_cast<const Stmt *>(); } + const Decl *asDecl() const { return Source.dyn_cast<const Decl *>(); } + const Expr *asExpr() const; + + operator bool() const { return !Source.isNull(); } + +private: + llvm::PointerUnion<const Decl *, const Stmt *> Source; +}; + +using SourceMap = std::vector<std::pair<unsigned, SourceInfo>>; + +/// Interface for classes which map locations to sources. +class SourceMapper { +public: + virtual ~SourceMapper() {} + + /// Returns source information for a given PC in a function. + virtual SourceInfo getSource(Function *F, CodePtr PC) const = 0; + + /// Returns the expression if an opcode belongs to one, null otherwise. + const Expr *getExpr(Function *F, CodePtr PC) const; + /// Returns the location from which an opcode originates. + SourceLocation getLocation(Function *F, CodePtr PC) const; +}; + +} // namespace interp +} // namespace clang + +#endif diff --git a/clang/lib/AST/Interp/State.cpp b/clang/lib/AST/Interp/State.cpp new file mode 100644 index 000000000000..692cc2e8d69b --- /dev/null +++ b/clang/lib/AST/Interp/State.cpp @@ -0,0 +1,158 @@ +//===--- State.cpp - State chain for the VM and AST Walker ------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "State.h" +#include "Frame.h" +#include "Program.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/CXXInheritance.h" + +using namespace clang; +using namespace clang::interp; + +State::~State() {} + +OptionalDiagnostic State::FFDiag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes) { + return diag(Loc, DiagId, ExtraNotes, false); +} + +OptionalDiagnostic State::FFDiag(const Expr *E, diag::kind DiagId, + unsigned ExtraNotes) { + if (getEvalStatus().Diag) + return diag(E->getExprLoc(), DiagId, ExtraNotes, false); + setActiveDiagnostic(false); + return OptionalDiagnostic(); +} + +OptionalDiagnostic State::FFDiag(const SourceInfo &SI, diag::kind DiagId, + unsigned ExtraNotes) { + if (getEvalStatus().Diag) + return diag(SI.getLoc(), DiagId, ExtraNotes, false); + setActiveDiagnostic(false); + return OptionalDiagnostic(); +} + +OptionalDiagnostic State::CCEDiag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes) { + // Don't override a previous diagnostic. Don't bother collecting + // diagnostics if we're evaluating for overflow. + if (!getEvalStatus().Diag || !getEvalStatus().Diag->empty()) { + setActiveDiagnostic(false); + return OptionalDiagnostic(); + } + return diag(Loc, DiagId, ExtraNotes, true); +} + +OptionalDiagnostic State::CCEDiag(const Expr *E, diag::kind DiagId, + unsigned ExtraNotes) { + return CCEDiag(E->getExprLoc(), DiagId, ExtraNotes); +} + +OptionalDiagnostic State::CCEDiag(const SourceInfo &SI, diag::kind DiagId, + unsigned ExtraNotes) { + return CCEDiag(SI.getLoc(), DiagId, ExtraNotes); +} + +OptionalDiagnostic State::Note(SourceLocation Loc, diag::kind DiagId) { + if (!hasActiveDiagnostic()) + return OptionalDiagnostic(); + return OptionalDiagnostic(&addDiag(Loc, DiagId)); +} + +void State::addNotes(ArrayRef<PartialDiagnosticAt> Diags) { + if (hasActiveDiagnostic()) { + getEvalStatus().Diag->insert(getEvalStatus().Diag->end(), Diags.begin(), + Diags.end()); + } +} + +DiagnosticBuilder State::report(SourceLocation Loc, diag::kind DiagId) { + return getCtx().getDiagnostics().Report(Loc, DiagId); +} + +/// Add a diagnostic to the diagnostics list. +PartialDiagnostic &State::addDiag(SourceLocation Loc, diag::kind DiagId) { + PartialDiagnostic PD(DiagId, getCtx().getDiagAllocator()); + getEvalStatus().Diag->push_back(std::make_pair(Loc, PD)); + return getEvalStatus().Diag->back().second; +} + +OptionalDiagnostic State::diag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes, bool IsCCEDiag) { + Expr::EvalStatus &EvalStatus = getEvalStatus(); + if (EvalStatus.Diag) { + if (hasPriorDiagnostic()) { + return OptionalDiagnostic(); + } + + unsigned CallStackNotes = getCallStackDepth() - 1; + unsigned Limit = getCtx().getDiagnostics().getConstexprBacktraceLimit(); + if (Limit) + CallStackNotes = std::min(CallStackNotes, Limit + 1); + if (checkingPotentialConstantExpression()) + CallStackNotes = 0; + + setActiveDiagnostic(true); + setFoldFailureDiagnostic(!IsCCEDiag); + EvalStatus.Diag->clear(); + EvalStatus.Diag->reserve(1 + ExtraNotes + CallStackNotes); + addDiag(Loc, DiagId); + if (!checkingPotentialConstantExpression()) { + addCallStack(Limit); + } + return OptionalDiagnostic(&(*EvalStatus.Diag)[0].second); + } + setActiveDiagnostic(false); + return OptionalDiagnostic(); +} + +const LangOptions &State::getLangOpts() const { return getCtx().getLangOpts(); } + +void State::addCallStack(unsigned Limit) { + // Determine which calls to skip, if any. + unsigned ActiveCalls = getCallStackDepth() - 1; + unsigned SkipStart = ActiveCalls, SkipEnd = SkipStart; + if (Limit && Limit < ActiveCalls) { + SkipStart = Limit / 2 + Limit % 2; + SkipEnd = ActiveCalls - Limit / 2; + } + + // Walk the call stack and add the diagnostics. + unsigned CallIdx = 0; + Frame *Top = getCurrentFrame(); + const Frame *Bottom = getBottomFrame(); + for (Frame *F = Top; F != Bottom; F = F->getCaller(), ++CallIdx) { + SourceLocation CallLocation = F->getCallLocation(); + + // Skip this call? + if (CallIdx >= SkipStart && CallIdx < SkipEnd) { + if (CallIdx == SkipStart) { + // Note that we're skipping calls. + addDiag(CallLocation, diag::note_constexpr_calls_suppressed) + << unsigned(ActiveCalls - Limit); + } + continue; + } + + // Use a different note for an inheriting constructor, because from the + // user's perspective it's not really a function at all. + if (auto *CD = dyn_cast_or_null<CXXConstructorDecl>(F->getCallee())) { + if (CD->isInheritingConstructor()) { + addDiag(CallLocation, diag::note_constexpr_inherited_ctor_call_here) + << CD->getParent(); + continue; + } + } + + SmallVector<char, 128> Buffer; + llvm::raw_svector_ostream Out(Buffer); + F->describe(Out); + addDiag(CallLocation, diag::note_constexpr_call_here) << Out.str(); + } +} diff --git a/clang/lib/AST/Interp/State.h b/clang/lib/AST/Interp/State.h new file mode 100644 index 000000000000..d9a645a3eb3e --- /dev/null +++ b/clang/lib/AST/Interp/State.h @@ -0,0 +1,133 @@ +//===--- State.h - State chain for the VM and AST Walker --------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines the base class of the interpreter and evaluator state. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_AST_INTERP_STATE_H +#define LLVM_CLANG_AST_INTERP_STATE_H + +#include "clang/AST/ASTDiagnostic.h" +#include "clang/AST/Expr.h" +#include "clang/AST/OptionalDiagnostic.h" + +namespace clang { + +/// Kinds of access we can perform on an object, for diagnostics. Note that +/// we consider a member function call to be a kind of access, even though +/// it is not formally an access of the object, because it has (largely) the +/// same set of semantic restrictions. +enum AccessKinds { + AK_Read, + AK_ReadObjectRepresentation, + AK_Assign, + AK_Increment, + AK_Decrement, + AK_MemberCall, + AK_DynamicCast, + AK_TypeId, + AK_Construct, + AK_Destroy, +}; + +// The order of this enum is important for diagnostics. +enum CheckSubobjectKind { + CSK_Base, + CSK_Derived, + CSK_Field, + CSK_ArrayToPointer, + CSK_ArrayIndex, + CSK_Real, + CSK_Imag +}; + +namespace interp { +class Frame; +class SourceInfo; + +/// Interface for the VM to interact with the AST walker's context. +class State { +public: + virtual ~State(); + + virtual bool checkingForUndefinedBehavior() const = 0; + virtual bool checkingPotentialConstantExpression() const = 0; + virtual bool noteUndefinedBehavior() = 0; + virtual bool keepEvaluatingAfterFailure() const = 0; + virtual Frame *getCurrentFrame() = 0; + virtual const Frame *getBottomFrame() const = 0; + virtual bool hasActiveDiagnostic() = 0; + virtual void setActiveDiagnostic(bool Flag) = 0; + virtual void setFoldFailureDiagnostic(bool Flag) = 0; + virtual Expr::EvalStatus &getEvalStatus() const = 0; + virtual ASTContext &getCtx() const = 0; + virtual bool hasPriorDiagnostic() = 0; + virtual unsigned getCallStackDepth() = 0; + +public: + // Diagnose that the evaluation could not be folded (FF => FoldFailure) + OptionalDiagnostic + FFDiag(SourceLocation Loc, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + FFDiag(const Expr *E, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + FFDiag(const SourceInfo &SI, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + /// Diagnose that the evaluation does not produce a C++11 core constant + /// expression. + /// + /// FIXME: Stop evaluating if we're in EM_ConstantExpression or + /// EM_PotentialConstantExpression mode and we produce one of these. + OptionalDiagnostic + CCEDiag(SourceLocation Loc, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + CCEDiag(const Expr *E, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + OptionalDiagnostic + CCEDiag(const SourceInfo &SI, + diag::kind DiagId = diag::note_invalid_subexpr_in_const_expr, + unsigned ExtraNotes = 0); + + /// Add a note to a prior diagnostic. + OptionalDiagnostic Note(SourceLocation Loc, diag::kind DiagId); + + /// Add a stack of notes to a prior diagnostic. + void addNotes(ArrayRef<PartialDiagnosticAt> Diags); + + /// Directly reports a diagnostic message. + DiagnosticBuilder report(SourceLocation Loc, diag::kind DiagId); + + const LangOptions &getLangOpts() const; + +private: + void addCallStack(unsigned Limit); + + PartialDiagnostic &addDiag(SourceLocation Loc, diag::kind DiagId); + + OptionalDiagnostic diag(SourceLocation Loc, diag::kind DiagId, + unsigned ExtraNotes, bool IsCCEDiag); +}; + +} // namespace interp +} // namespace clang + +#endif |