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