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 
21 namespace clang {
22 namespace interp {
23 
24 /// Stack frame storing temporaries and parameters.
25 class InterpStack final {
26 public:
27   InterpStack() {}
28 
29   /// Destroys the stack, freeing up storage.
30   ~InterpStack();
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 
95 private:
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
196