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 "PrimType.h" 17 #include <memory> 18 #include <vector> 19 20 namespace clang { 21 namespace interp { 22 23 /// Stack frame storing temporaries and parameters. 24 class InterpStack final { 25 public: 26 InterpStack() {} 27 28 /// Destroys the stack, freeing up storage. 29 ~InterpStack(); 30 31 /// Constructs a value in place on the top of the stack. 32 template <typename T, typename... Tys> void push(Tys &&... Args) { 33 new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...); 34 #ifndef NDEBUG 35 ItemTypes.push_back(toPrimType<T>()); 36 #endif 37 } 38 39 /// Returns the value from the top of the stack and removes it. 40 template <typename T> T pop() { 41 #ifndef NDEBUG 42 assert(!ItemTypes.empty()); 43 assert(ItemTypes.back() == toPrimType<T>()); 44 ItemTypes.pop_back(); 45 #endif 46 auto *Ptr = &peek<T>(); 47 auto Value = std::move(*Ptr); 48 Ptr->~T(); 49 shrink(aligned_size<T>()); 50 return Value; 51 } 52 53 /// Discards the top value from the stack. 54 template <typename T> void discard() { 55 #ifndef NDEBUG 56 assert(ItemTypes.back() == toPrimType<T>()); 57 ItemTypes.pop_back(); 58 #endif 59 auto *Ptr = &peek<T>(); 60 Ptr->~T(); 61 shrink(aligned_size<T>()); 62 } 63 64 /// Returns a reference to the value on the top of the stack. 65 template <typename T> T &peek() const { 66 return *reinterpret_cast<T *>(peek(aligned_size<T>())); 67 } 68 69 /// Returns a pointer to the top object. 70 void *top() const { return Chunk ? peek(0) : nullptr; } 71 72 /// Returns the size of the stack in bytes. 73 size_t size() const { return StackSize; } 74 75 /// Clears the stack without calling any destructors. 76 void clear(); 77 78 // Returns whether the stack is empty. 79 bool empty() const { return StackSize == 0; } 80 81 private: 82 /// All stack slots are aligned to the native pointer alignment for storage. 83 /// The size of an object is rounded up to a pointer alignment multiple. 84 template <typename T> constexpr size_t aligned_size() const { 85 constexpr size_t PtrAlign = alignof(void *); 86 return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign; 87 } 88 89 /// Grows the stack to accommodate a value and returns a pointer to it. 90 void *grow(size_t Size); 91 /// Returns a pointer from the top of the stack. 92 void *peek(size_t Size) const; 93 /// Shrinks the stack. 94 void shrink(size_t Size); 95 96 /// Allocate stack space in 1Mb chunks. 97 static constexpr size_t ChunkSize = 1024 * 1024; 98 99 /// Metadata for each stack chunk. 100 /// 101 /// The stack is composed of a linked list of chunks. Whenever an allocation 102 /// is out of bounds, a new chunk is linked. When a chunk becomes empty, 103 /// it is not immediately freed: a chunk is deallocated only when the 104 /// predecessor becomes empty. 105 struct StackChunk { 106 StackChunk *Next; 107 StackChunk *Prev; 108 char *End; 109 110 StackChunk(StackChunk *Prev = nullptr) 111 : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {} 112 113 /// Returns the size of the chunk, minus the header. 114 size_t size() const { return End - start(); } 115 116 /// Returns a pointer to the start of the data region. 117 char *start() { return reinterpret_cast<char *>(this + 1); } 118 const char *start() const { 119 return reinterpret_cast<const char *>(this + 1); 120 } 121 }; 122 static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size"); 123 124 /// First chunk on the stack. 125 StackChunk *Chunk = nullptr; 126 /// Total size of the stack. 127 size_t StackSize = 0; 128 129 #ifndef NDEBUG 130 /// vector recording the type of data we pushed into the stack. 131 std::vector<PrimType> ItemTypes; 132 133 template <typename T> static constexpr PrimType toPrimType() { 134 if constexpr (std::is_same_v<T, Pointer>) 135 return PT_Ptr; 136 else if constexpr (std::is_same_v<T, bool> || 137 std::is_same_v<T, Boolean>) 138 return PT_Bool; 139 else if constexpr (std::is_same_v<T, int8_t> || 140 std::is_same_v<T, Integral<8, true>>) 141 return PT_Sint8; 142 else if constexpr (std::is_same_v<T, uint8_t> || 143 std::is_same_v<T, Integral<8, false>>) 144 return PT_Uint8; 145 else if constexpr (std::is_same_v<T, int16_t> || 146 std::is_same_v<T, Integral<16, true>>) 147 return PT_Sint16; 148 else if constexpr (std::is_same_v<T, uint16_t> || 149 std::is_same_v<T, Integral<16, false>>) 150 return PT_Uint16; 151 else if constexpr (std::is_same_v<T, int32_t> || 152 std::is_same_v<T, Integral<32, true>>) 153 return PT_Sint32; 154 else if constexpr (std::is_same_v<T, uint32_t> || 155 std::is_same_v<T, Integral<32, false>>) 156 return PT_Uint32; 157 else if constexpr (std::is_same_v<T, int64_t> || 158 std::is_same_v<T, Integral<64, true>>) 159 return PT_Sint64; 160 else if constexpr (std::is_same_v<T, uint64_t> || 161 std::is_same_v<T, Integral<64, false>>) 162 return PT_Uint64; 163 164 llvm_unreachable("unknown type push()'ed into InterpStack"); 165 } 166 #endif 167 }; 168 169 } // namespace interp 170 } // namespace clang 171 172 #endif 173