1*06f32e7eSjoerg //===--- InterpStack.h - Stack implementation for the VM --------*- C++ -*-===// 2*06f32e7eSjoerg // 3*06f32e7eSjoerg // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*06f32e7eSjoerg // See https://llvm.org/LICENSE.txt for license information. 5*06f32e7eSjoerg // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*06f32e7eSjoerg // 7*06f32e7eSjoerg //===----------------------------------------------------------------------===// 8*06f32e7eSjoerg // 9*06f32e7eSjoerg // Defines the upwards-growing stack used by the interpreter. 10*06f32e7eSjoerg // 11*06f32e7eSjoerg //===----------------------------------------------------------------------===// 12*06f32e7eSjoerg 13*06f32e7eSjoerg #ifndef LLVM_CLANG_AST_INTERP_INTERPSTACK_H 14*06f32e7eSjoerg #define LLVM_CLANG_AST_INTERP_INTERPSTACK_H 15*06f32e7eSjoerg 16*06f32e7eSjoerg #include <memory> 17*06f32e7eSjoerg 18*06f32e7eSjoerg namespace clang { 19*06f32e7eSjoerg namespace interp { 20*06f32e7eSjoerg 21*06f32e7eSjoerg /// Stack frame storing temporaries and parameters. 22*06f32e7eSjoerg class InterpStack final { 23*06f32e7eSjoerg public: InterpStack()24*06f32e7eSjoerg InterpStack() {} 25*06f32e7eSjoerg 26*06f32e7eSjoerg /// Destroys the stack, freeing up storage. 27*06f32e7eSjoerg ~InterpStack(); 28*06f32e7eSjoerg 29*06f32e7eSjoerg /// Constructs a value in place on the top of the stack. push(Tys &&...Args)30*06f32e7eSjoerg template <typename T, typename... Tys> void push(Tys &&... Args) { 31*06f32e7eSjoerg new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...); 32*06f32e7eSjoerg } 33*06f32e7eSjoerg 34*06f32e7eSjoerg /// Returns the value from the top of the stack and removes it. pop()35*06f32e7eSjoerg template <typename T> T pop() { 36*06f32e7eSjoerg auto *Ptr = &peek<T>(); 37*06f32e7eSjoerg auto Value = std::move(*Ptr); 38*06f32e7eSjoerg Ptr->~T(); 39*06f32e7eSjoerg shrink(aligned_size<T>()); 40*06f32e7eSjoerg return Value; 41*06f32e7eSjoerg } 42*06f32e7eSjoerg 43*06f32e7eSjoerg /// Discards the top value from the stack. discard()44*06f32e7eSjoerg template <typename T> void discard() { 45*06f32e7eSjoerg auto *Ptr = &peek<T>(); 46*06f32e7eSjoerg Ptr->~T(); 47*06f32e7eSjoerg shrink(aligned_size<T>()); 48*06f32e7eSjoerg } 49*06f32e7eSjoerg 50*06f32e7eSjoerg /// Returns a reference to the value on the top of the stack. peek()51*06f32e7eSjoerg template <typename T> T &peek() { 52*06f32e7eSjoerg return *reinterpret_cast<T *>(peek(aligned_size<T>())); 53*06f32e7eSjoerg } 54*06f32e7eSjoerg 55*06f32e7eSjoerg /// Returns a pointer to the top object. top()56*06f32e7eSjoerg void *top() { return Chunk ? peek(0) : nullptr; } 57*06f32e7eSjoerg 58*06f32e7eSjoerg /// Returns the size of the stack in bytes. size()59*06f32e7eSjoerg size_t size() const { return StackSize; } 60*06f32e7eSjoerg 61*06f32e7eSjoerg /// Clears the stack without calling any destructors. 62*06f32e7eSjoerg void clear(); 63*06f32e7eSjoerg 64*06f32e7eSjoerg private: 65*06f32e7eSjoerg /// All stack slots are aligned to the native pointer alignment for storage. 66*06f32e7eSjoerg /// The size of an object is rounded up to a pointer alignment multiple. aligned_size()67*06f32e7eSjoerg template <typename T> constexpr size_t aligned_size() const { 68*06f32e7eSjoerg constexpr size_t PtrAlign = alignof(void *); 69*06f32e7eSjoerg return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign; 70*06f32e7eSjoerg } 71*06f32e7eSjoerg 72*06f32e7eSjoerg /// Grows the stack to accomodate a value and returns a pointer to it. 73*06f32e7eSjoerg void *grow(size_t Size); 74*06f32e7eSjoerg /// Returns a pointer from the top of the stack. 75*06f32e7eSjoerg void *peek(size_t Size); 76*06f32e7eSjoerg /// Shrinks the stack. 77*06f32e7eSjoerg void shrink(size_t Size); 78*06f32e7eSjoerg 79*06f32e7eSjoerg /// Allocate stack space in 1Mb chunks. 80*06f32e7eSjoerg static constexpr size_t ChunkSize = 1024 * 1024; 81*06f32e7eSjoerg 82*06f32e7eSjoerg /// Metadata for each stack chunk. 83*06f32e7eSjoerg /// 84*06f32e7eSjoerg /// The stack is composed of a linked list of chunks. Whenever an allocation 85*06f32e7eSjoerg /// is out of bounds, a new chunk is linked. When a chunk becomes empty, 86*06f32e7eSjoerg /// it is not immediately freed: a chunk is deallocated only when the 87*06f32e7eSjoerg /// predecessor becomes empty. 88*06f32e7eSjoerg struct StackChunk { 89*06f32e7eSjoerg StackChunk *Next; 90*06f32e7eSjoerg StackChunk *Prev; 91*06f32e7eSjoerg char *End; 92*06f32e7eSjoerg 93*06f32e7eSjoerg StackChunk(StackChunk *Prev = nullptr) NextStackChunk94*06f32e7eSjoerg : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {} 95*06f32e7eSjoerg 96*06f32e7eSjoerg /// Returns the size of the chunk, minus the header. sizeStackChunk97*06f32e7eSjoerg size_t size() { return End - start(); } 98*06f32e7eSjoerg 99*06f32e7eSjoerg /// Returns a pointer to the start of the data region. startStackChunk100*06f32e7eSjoerg char *start() { return reinterpret_cast<char *>(this + 1); } 101*06f32e7eSjoerg }; 102*06f32e7eSjoerg static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size"); 103*06f32e7eSjoerg 104*06f32e7eSjoerg /// First chunk on the stack. 105*06f32e7eSjoerg StackChunk *Chunk = nullptr; 106*06f32e7eSjoerg /// Total size of the stack. 107*06f32e7eSjoerg size_t StackSize = 0; 108*06f32e7eSjoerg }; 109*06f32e7eSjoerg 110*06f32e7eSjoerg } // namespace interp 111*06f32e7eSjoerg } // namespace clang 112*06f32e7eSjoerg 113*06f32e7eSjoerg #endif 114