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