clang 18.0.0git
InterpStack.h
Go to the documentation of this file.
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
21namespace clang {
22namespace interp {
23
24/// Stack frame storing temporaries and parameters.
25class InterpStack final {
26public:
28
29 /// Destroys the stack, freeing up storage.
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
95private:
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
Stack frame storing temporaries and parameters.
Definition: InterpStack.h:25
T pop()
Returns the value from the top of the stack and removes it.
Definition: InterpStack.h:41
T & peek(size_t Offset) const
Definition: InterpStack.h:75
void dump() const
dump the stack contents to stderr.
Definition: InterpStack.cpp:86
void push(Tys &&... Args)
Constructs a value in place on the top of the stack.
Definition: InterpStack.h:33
void * top() const
Returns a pointer to the top object.
Definition: InterpStack.h:81
void clear()
Clears the stack without calling any destructors.
Definition: InterpStack.cpp:23
size_t size() const
Returns the size of the stack in bytes.
Definition: InterpStack.h:84
bool empty() const
Returns whether the stack is empty.
Definition: InterpStack.h:90
void discard()
Discards the top value from the stack.
Definition: InterpStack.h:55
~InterpStack()
Destroys the stack, freeing up storage.
Definition: InterpStack.cpp:19
T & peek() const
Returns a reference to the value on the top of the stack.
Definition: InterpStack.h:67
constexpr bool aligned(uintptr_t Value)
Definition: PrimType.h:86
PrimType
Enumeration of the primitive types of the VM.
Definition: PrimType.h:31