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