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 
22 namespace clang {
23 namespace interp {
24 
25 /// Stack frame storing temporaries and parameters.
26 class InterpStack final {
27 public:
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(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(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(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(Offset));
79   }
80 
81   /// Returns a pointer to the top object.
82   void *top() const { return Chunk ? peekData(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 
96 private:
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(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