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