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