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 <memory>
17 
18 namespace clang {
19 namespace interp {
20 
21 /// Stack frame storing temporaries and parameters.
22 class InterpStack final {
23 public:
24   InterpStack() {}
25 
26   /// Destroys the stack, freeing up storage.
27   ~InterpStack();
28 
29   /// Constructs a value in place on the top of the stack.
30   template <typename T, typename... Tys> void push(Tys &&... Args) {
31     new (grow(aligned_size<T>())) T(std::forward<Tys>(Args)...);
32   }
33 
34   /// Returns the value from the top of the stack and removes it.
35   template <typename T> T pop() {
36     auto *Ptr = &peek<T>();
37     auto Value = std::move(*Ptr);
38     Ptr->~T();
39     shrink(aligned_size<T>());
40     return Value;
41   }
42 
43   /// Discards the top value from the stack.
44   template <typename T> void discard() {
45     auto *Ptr = &peek<T>();
46     Ptr->~T();
47     shrink(aligned_size<T>());
48   }
49 
50   /// Returns a reference to the value on the top of the stack.
51   template <typename T> T &peek() {
52     return *reinterpret_cast<T *>(peek(aligned_size<T>()));
53   }
54 
55   /// Returns a pointer to the top object.
56   void *top() { return Chunk ? peek(0) : nullptr; }
57 
58   /// Returns the size of the stack in bytes.
59   size_t size() const { return StackSize; }
60 
61   /// Clears the stack without calling any destructors.
62   void clear();
63 
64 private:
65   /// All stack slots are aligned to the native pointer alignment for storage.
66   /// The size of an object is rounded up to a pointer alignment multiple.
67   template <typename T> constexpr size_t aligned_size() const {
68     constexpr size_t PtrAlign = alignof(void *);
69     return ((sizeof(T) + PtrAlign - 1) / PtrAlign) * PtrAlign;
70   }
71 
72   /// Grows the stack to accommodate a value and returns a pointer to it.
73   void *grow(size_t Size);
74   /// Returns a pointer from the top of the stack.
75   void *peek(size_t Size);
76   /// Shrinks the stack.
77   void shrink(size_t Size);
78 
79   /// Allocate stack space in 1Mb chunks.
80   static constexpr size_t ChunkSize = 1024 * 1024;
81 
82   /// Metadata for each stack chunk.
83   ///
84   /// The stack is composed of a linked list of chunks. Whenever an allocation
85   /// is out of bounds, a new chunk is linked. When a chunk becomes empty,
86   /// it is not immediately freed: a chunk is deallocated only when the
87   /// predecessor becomes empty.
88   struct StackChunk {
89     StackChunk *Next;
90     StackChunk *Prev;
91     char *End;
92 
93     StackChunk(StackChunk *Prev = nullptr)
94         : Next(nullptr), Prev(Prev), End(reinterpret_cast<char *>(this + 1)) {}
95 
96     /// Returns the size of the chunk, minus the header.
97     size_t size() { return End - start(); }
98 
99     /// Returns a pointer to the start of the data region.
100     char *start() { return reinterpret_cast<char *>(this + 1); }
101   };
102   static_assert(sizeof(StackChunk) < ChunkSize, "Invalid chunk size");
103 
104   /// First chunk on the stack.
105   StackChunk *Chunk = nullptr;
106   /// Total size of the stack.
107   size_t StackSize = 0;
108 };
109 
110 } // namespace interp
111 } // namespace clang
112 
113 #endif
114