219 lines · c
1//===--- InterpStack.h - Stack implementation for the VM --------*- C++ -*-===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9// Defines the upwards-growing stack used by the interpreter.10//11//===----------------------------------------------------------------------===//12 13#ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H14#define LLVM_CLANG_AST_INTERP_INTERPSTACK_H15 16#include "FixedPoint.h"17#include "IntegralAP.h"18#include "MemberPointer.h"19#include "PrimType.h"20 21namespace clang {22namespace interp {23 24/// Stack frame storing temporaries and parameters.25class InterpStack final {26public:27 InterpStack() = default;28 29 /// Destroys the stack, freeing up storage.30 ~InterpStack();31 32 /// Constructs a value in place on the top of the stack.33 template <typename T, typename... Tys> void push(Tys &&...Args) {34 new (grow<aligned_size<T>()>()) T(std::forward<Tys>(Args)...);35 ItemTypes.push_back(toPrimType<T>());36 }37 38 /// Returns the value from the top of the stack and removes it.39 template <typename T> T pop() {40 assert(!ItemTypes.empty());41 assert(ItemTypes.back() == toPrimType<T>());42 ItemTypes.pop_back();43 T *Ptr = &peekInternal<T>();44 T Value = std::move(*Ptr);45 shrink(aligned_size<T>());46 return Value;47 }48 49 /// Discards the top value from the stack.50 template <typename T> void discard() {51 assert(!ItemTypes.empty());52 assert(ItemTypes.back() == toPrimType<T>());53 ItemTypes.pop_back();54 T *Ptr = &peekInternal<T>();55 if constexpr (!std::is_trivially_destructible_v<T>) {56 Ptr->~T();57 }58 shrink(aligned_size<T>());59 }60 61 /// Returns a reference to the value on the top of the stack.62 template <typename T> T &peek() const {63 assert(!ItemTypes.empty());64 assert(ItemTypes.back() == toPrimType<T>());65 return peekInternal<T>();66 }67 68 template <typename T> T &peek(size_t Offset) const {69 assert(aligned(Offset));70 return *reinterpret_cast<T *>(peekData(Offset));71 }72 73 /// Returns a pointer to the top object.74 void *top() const { return Chunk ? peekData(0) : nullptr; }75 76 /// Returns the size of the stack in bytes.77 size_t size() const { return StackSize; }78 79 /// Clears the stack.80 void clear();81 void clearTo(size_t NewSize);82 83 /// Returns whether the stack is empty.84 bool empty() const { return StackSize == 0; }85 86 /// dump the stack contents to stderr.87 void dump() const;88 89private:90 /// All stack slots are aligned to the native pointer alignment for storage.91 /// The size of an object is rounded up to a pointer alignment multiple.92 template <typename T> static constexpr size_t aligned_size() {93 constexpr size_t PtrAlign = alignof(void *);94 return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign;95 }96 97 /// Like the public peek(), but without the debug type checks.98 template <typename T> T &peekInternal() const {99 return *reinterpret_cast<T *>(peekData(aligned_size<T>()));100 }101 102 /// Grows the stack to accommodate a value and returns a pointer to it.103 template <size_t Size> void *grow() {104 assert(Size < ChunkSize - sizeof(StackChunk) && "Object too large");105 static_assert(aligned(Size));106 107 // Allocate a new stack chunk if necessary.108 if (LLVM_UNLIKELY(!Chunk)) {109 Chunk = new (std::malloc(ChunkSize)) StackChunk(Chunk);110 } else if (LLVM_UNLIKELY(Chunk->size() >111 ChunkSize - sizeof(StackChunk) - Size)) {112 if (Chunk->Next) {113 Chunk = Chunk->Next;114 } else {115 StackChunk *Next = new (std::malloc(ChunkSize)) StackChunk(Chunk);116 Chunk->Next = Next;117 Chunk = Next;118 }119 }120 121 auto *Object = reinterpret_cast<void *>(Chunk->start() + Chunk->Size);122 Chunk->Size += Size;123 StackSize += Size;124 return Object;125 }126 127 /// Returns a pointer from the top of the stack.128 void *peekData(size_t Size) const;129 /// Shrinks the stack.130 void shrink(size_t Size);131 132 /// Allocate stack space in 1Mb chunks.133 static constexpr size_t ChunkSize = 1024 * 1024;134 135 /// Metadata for each stack chunk.136 ///137 /// The stack is composed of a linked list of chunks. Whenever an allocation138 /// is out of bounds, a new chunk is linked. When a chunk becomes empty,139 /// it is not immediately freed: a chunk is deallocated only when the140 /// predecessor becomes empty.141 struct StackChunk {142 StackChunk *Next;143 StackChunk *Prev;144 uint32_t Size;145 146 StackChunk(StackChunk *Prev = nullptr)147 : Next(nullptr), Prev(Prev), Size(0) {}148 149 /// Returns the size of the chunk, minus the header.150 size_t size() const { return Size; }151 152 /// Returns a pointer to the start of the data region.153 char *start() { return reinterpret_cast<char *>(this + 1); }154 const char *start() const {155 return reinterpret_cast<const char *>(this + 1);156 }157 };158 static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size");159 160 /// First chunk on the stack.161 StackChunk *Chunk = nullptr;162 /// Total size of the stack.163 size_t StackSize = 0;164 165 /// SmallVector recording the type of data we pushed into the stack.166 /// We don't usually need this during normal code interpretation but167 /// when aborting, we need type information to call the destructors168 /// for what's left on the stack.169 llvm::SmallVector<PrimType> ItemTypes;170 171 template <typename T> static constexpr PrimType toPrimType() {172 if constexpr (std::is_same_v<T, Pointer>)173 return PT_Ptr;174 else if constexpr (std::is_same_v<T, bool> || std::is_same_v<T, Boolean>)175 return PT_Bool;176 else if constexpr (std::is_same_v<T, int8_t> ||177 std::is_same_v<T, Integral<8, true>>)178 return PT_Sint8;179 else if constexpr (std::is_same_v<T, uint8_t> ||180 std::is_same_v<T, Integral<8, false>>)181 return PT_Uint8;182 else if constexpr (std::is_same_v<T, int16_t> ||183 std::is_same_v<T, Integral<16, true>>)184 return PT_Sint16;185 else if constexpr (std::is_same_v<T, uint16_t> ||186 std::is_same_v<T, Integral<16, false>>)187 return PT_Uint16;188 else if constexpr (std::is_same_v<T, int32_t> ||189 std::is_same_v<T, Integral<32, true>>)190 return PT_Sint32;191 else if constexpr (std::is_same_v<T, uint32_t> ||192 std::is_same_v<T, Integral<32, false>>)193 return PT_Uint32;194 else if constexpr (std::is_same_v<T, int64_t> ||195 std::is_same_v<T, Integral<64, true>>)196 return PT_Sint64;197 else if constexpr (std::is_same_v<T, uint64_t> ||198 std::is_same_v<T, Integral<64, false>>)199 return PT_Uint64;200 else if constexpr (std::is_same_v<T, Floating>)201 return PT_Float;202 else if constexpr (std::is_same_v<T, IntegralAP<true>>)203 return PT_IntAP;204 else if constexpr (std::is_same_v<T, IntegralAP<false>>)205 return PT_IntAP;206 else if constexpr (std::is_same_v<T, MemberPointer>)207 return PT_MemberPtr;208 else if constexpr (std::is_same_v<T, FixedPoint>)209 return PT_FixedPoint;210 211 llvm_unreachable("unknown type push()'ed into InterpStack");212 }213};214 215} // namespace interp216} // namespace clang217 218#endif219