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