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