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 "PrimType.h"
19#include <memory>
20#include <vector>
21
22namespace clang {
23namespace interp {
24
25/// Stack frame storing temporaries and parameters.
26class InterpStack final {
27public:
28 InterpStack() {}
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(Size: aligned_size<T>())) T(std::forward<Tys>(Args)...);
36#ifndef NDEBUG
37 ItemTypes.push_back(toPrimType<T>());
38#endif
39 }
40
41 /// Returns the value from the top of the stack and removes it.
42 template <typename T> T pop() {
43#ifndef NDEBUG
44 assert(!ItemTypes.empty());
45 assert(ItemTypes.back() == toPrimType<T>());
46 ItemTypes.pop_back();
47#endif
48 T *Ptr = &peekInternal<T>();
49 T Value = std::move(*Ptr);
50 Ptr->~T();
51 shrink(Size: aligned_size<T>());
52 return Value;
53 }
54
55 /// Discards the top value from the stack.
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(Size: aligned_size<T>());
65 }
66
67 /// Returns a reference to the value on the top of the stack.
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
76 template <typename T> T &peek(size_t Offset) const {
77 assert(aligned(Offset));
78 return *reinterpret_cast<T *>(peekData(Size: Offset));
79 }
80
81 /// Returns a pointer to the top object.
82 void *top() const { return Chunk ? peekData(Size: 0) : nullptr; }
83
84 /// Returns the size of the stack in bytes.
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.
91 bool empty() const { return StackSize == 0; }
92
93 /// dump the stack contents to stderr.
94 void dump() const;
95
96private:
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.
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.
105 template <typename T> T &peekInternal() const {
106 return *reinterpret_cast<T *>(peekData(Size: 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)
131 : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {}
132
133 /// Returns the size of the chunk, minus the header.
134 size_t size() const { return End - start(); }
135
136 /// Returns a pointer to the start of the data region.
137 char *start() { return reinterpret_cast<char *>(this + 1); }
138 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
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
192 llvm_unreachable("unknown type push()'ed into InterpStack");
193 }
194#endif
195};
196
197} // namespace interp
198} // namespace clang
199
200#endif
201

source code of clang/lib/AST/Interp/InterpStack.h