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